Transportation Geography and Network Science/Dijkstra's Algorithm

Overview edit

Dijkstra's Algorithm is a widely-used graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. The algorithm was developed by Edsger W. Dijkstra in 1956 and is applicable to both directed and undirected graphs. It is often used in routing, as well as various applications that require finding the shortest path between nodes in a weighted graph.

Dijkstra's Algorithm for a Directed Graph edit

For the directed graph   defined previously, Dijkstra's Algorithm can be used to calculate the shortest (travel time) path between origin node   and every other node in the network. 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, the corresponding element in   is a very large number.

Let the set of nodes   be divided into two subsets:   and  .   represents the set of nodes for which the shortest path from   is known, and   is the complementary set of  . Let   represent a vector of permanent labels for nodes in  . The permanent label of a node is the shortest distance from the origin node  . Let   be the set of nodes adjacent to nodes in   along the shortest path. Let   be a vector of temporary labels for nodes in  . The following steps explain the algorithm:

  • Initialization: Set  , and assign a large number to all elements of  .
  • Node Exploration: Find all child nodes adjacent to any parent node   in   that are not already in   using the distance matrix  . Calculate a temporary label for each child node   by summing the permanent label of parent node   from vector   and the length of the link  .
  • Node Selection: Select the node with the smallest temporary label and add it to the end of the set  , removing it from  . Add the corresponding parent node   to the end of the set   and the corresponding temporary label to  . With the updated  , repeat steps 2 and 3 until there are no elements left in  .

To obtain the length of the shortest path from origin node   to any other node in the network, find the position of the destination node in   and read the corresponding element in  . To obtain the shortest path itself, find the position of the destination node   in  , read the element in the same position in  , and repeat the process until node   is reached in   (i.e., trace the shortest path backward until the origin is reached). The links along the shortest path from origin node   to destination node   calculated this way are assigned to a set  .

The above algorithm is performed for a single origin node  , but to obtain the shortest path from every node to every other node for trip distribution and traffic assignment, Dijkstra's Algorithm should be performed for every node in the graph  .

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

References edit