# Transportation Geography and Network Science/Algorithms

## Dijkstra's algorithm[edit]

The centrality measures requires finding the shortest path from one node to another. The most widely-used algorithm is Dijkstra's algorithm. A greedy algorithm, the Dijkstra's algorithm starts at the source node and gradually spans a tree to all nodes reachable. Nodes that provide the shortest distance in that round are added to the tree by sequence.

Dijkstra’s Algorithm is regarded as one of the most efficient algorithms to calculate the shortest path.

For the directed graph defined previously, a shortest (travel time) path between origin node to every other node in the network can be calculated using this algorithm. Let be the distance matrix of with representing the length (travel time) of the links from node to node , if nodes and are not connected then the corresponding element in is a very large number.

Say the set of nodes is divided into two different subsets and , where represents the set of nodes to which shortest path from is known and the complementary set of is . Let represent a vector of permanent labels of nodes corresponding to every node in **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle {\Omega_r}}**
. The permanent label of a node is the shortest distance of the node from the origin node . Say is the set of nodes that are adjacent to nodes in along the shortest path. Let **Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): \Lambda **
be a vector of temporary labels of nodes corresponding to nodes in . The steps involved in the algorithm are explained below.

- Initialize , and all elements of are assigned a large number.
- Find all the child nodes that are adjacent to any node – parent node - in that are not already in
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle {\Omega_r}}**using the distance matrix . Then calculate a temporary label to each of the child node by summing the permanent label of the parent node from the vector and length of the link**Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle i\rightarrow j\Delta _{ij}}**. - Select the node with smallest temporary label and add it at the end of the set , deleting it in . Then add the corresponding parent node at the end of the set and corresponding temporary label to . With the new
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle {\Omega_r}}**repeat the steps from 2 until there are no elements in .

To get the length of the shortest path from the origin node r to any other node in the network, look for the position of the destination node in and the corresponding element in gives the length of the shortest path. To get the shortest path itself, look for the position of the destination node s in

The above algorithm is done for a single origin node r, but the shortest path from every node to every other node is required for trip distribution and traffic assignment. In that case perform Dijkstra’s algorithm for every node in the graph .

Further details of the algorithm can be found in ^{[1]}.

## Community detection[edit]

The goal of community detection is to cluster the network into groups of nodes that have few connections between these nodes. ^{[2]}. A cluster is a collection of nodes that are similar in terms of connections. One basic algorithm to identify clusters is the hierarchical clustering algorithm which creates tree-structure hierarchy of clusters. The leaves are the nodes and the root is a single cluster consisting of all nodes. The hierarchies of leaves show the communities of different levels. The details about the algorithm can be found in Hierarchical clustering .

## References[edit]

- ↑ Dijkstra's algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- ↑ Newman, M.E. Networks. 2010. Oxford: Oxford University Press.