Transportation Geography and Network Science/Algorithms

From Wikibooks, open books for an open world
< Transportation Geography and Network Science
Jump to navigation Jump to search

Dijkstra's algorithm[edit | edit source]

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 . 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 be a vector of temporary labels of nodes corresponding to nodes in . The steps involved in the algorithm are explained below.

  1. Initialize , and all elements of are assigned a large number.
  2. Find all the child nodes that are adjacent to any node – parent node - in that are not already in 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 .
  3. 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 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 and read the element that occupies that same position in then again look for the position of this new node in and repeat the process until the node is reached in , i.e. tracing the shortest path backward until the origin is reached. The links that lie along the shortest path from origin node to destination node s calculated this way are assigned to a set .

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 | edit source]

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 | edit source]

  1. Dijkstra's algorithm
  2. Newman, M.E. Networks. 2010. Oxford: Oxford University Press.