Transportation Geography and Network Science/Dijkstra's Algorithm

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Overview[edit | edit source]

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

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