Transportation Geography and Network Science/Algorithms

< Transportation Geography and Network Science

Dijkstra's algorithm

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 ${G}$ defined previously, a shortest (travel time) path between origin node $r$ to every other node in the network can be calculated using this algorithm. Let $\Delta$ be the distance matrix of ${G}$ with $\Delta _{ij}$ representing the length (travel time) of the links from node $i$ to node $j$ , if nodes $i$ and $j$ are not connected then the corresponding element in $\Delta$ is a very large number.

Say the set of nodes ${N}$ is divided into two different subsets ${\Omega _{r}}$ and ${\Gamma _{r}}$ , where ${\Omega _{r}}$ represents the set of nodes to which shortest path from $r$ is known and the complementary set of ${\Omega _{r}}$ is ${\Gamma _{r}}$ . Let represent a vector of permanent labels of nodes corresponding to every node in ${\Omega _{r}}$ . The permanent label of a node is the shortest distance of the node from the origin node $r$ . Say ${\Phi _{r}}$ is the set of nodes that are adjacent to nodes in ${\Omega _{r}}$ along the shortest path. Let $\Lambda$ be a vector of temporary labels of nodes corresponding to nodes in ${\Gamma _{r}}$ . The steps involved in the algorithm are explained below.

Initialize ${\Omega _{r}}={r},={0},{\Phi _{r}}={0}$ , and all elements of $\Lambda$ are assigned a large number.
Find all the child nodes that are adjacent to any node $j$ – parent node - in ${\Omega _{r}}$ that are not already in ${\Omega _{r}}$ using the distance matrix $\Delta$ . Then calculate a temporary label to each of the child node $i$ by summing the permanent label of the parent node $j$ from the vector $\Pi _{r}$ and length of the link $i\rightarrow j\Delta _{ij}$ .
Select the node with smallest temporary label and add it at the end of the set ${\Omega _{r}}$ , deleting it in ${\Gamma _{r}}$ . Then add the corresponding parent node $j$ at the end of the set ${\Phi _{r}}$ and corresponding temporary label to $\Pi _{r}$ . With the new ${\Omega _{r}}$ repeat the steps from 2 until there are no elements in ${\Gamma _{r}}$ .

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 ${\Omega _{r}}$ 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 ${\Omega _{r}}$ and read the element that occupies that same position in ${\Phi _{r}}$ then again look for the position of this new node in ${\Omega _{r}}$ and repeat the process until the node $r$ is reached in ${\Phi _{r}}$ , i.e. tracing the shortest path backward until the origin is reached. The links that lie along the shortest path from origin node $r$ to destination node s calculated this way are assigned to a set ${K_{rs}}$ .

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 ${G}$ .

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

Community detection

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

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

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.