Transportation Geography and Network Science/Dijkstra's Algorithm

Overview

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

For the directed graph $G$ defined previously, Dijkstra's Algorithm can be used to calculate the shortest (travel time) path between origin node $r$ and every other node in the network. Let $\mathrm{\Delta }$ be the distance matrix of $G$ with ${\mathrm{\Delta }}_{ij}$ representing the length (travel time) of the links from node $i$ to node $j$. If nodes $i$ and $j$ are not connected, the corresponding element in $\mathrm{\Delta }$ is a very large number.

Let the set of nodes $N$ be divided into two subsets: ${\mathrm{\Omega }}_r$ and ${\mathrm{\Gamma }}_r$. ${\mathrm{\Omega }}_r$ represents the set of nodes for which the shortest path from $r$ is known, and ${\mathrm{\Gamma }}_r$ is the complementary set of ${\mathrm{\Omega }}_r$. Let ${\mathrm{\Pi }}_r$ represent a vector of permanent labels for nodes in ${\mathrm{\Omega }}_r$. The permanent label of a node is the shortest distance from the origin node $r$. Let ${\mathrm{\Phi }}_r$ be the set of nodes adjacent to nodes in ${\mathrm{\Omega }}_r$ along the shortest path. Let $\mathrm{\Lambda }$ be a vector of temporary labels for nodes in ${\mathrm{\Gamma }}_r$. The following steps explain the algorithm:

• Initialization: Set ${\mathrm{\Omega }}_r=r,{\mathrm{\Pi }}_r=0,{\mathrm{\Phi }}_r=0$, and assign a large number to all elements of $\mathrm{\Lambda }$.
• Node Exploration: Find all child nodes adjacent to any parent node $j$ in ${\mathrm{\Omega }}_r$ that are not already in ${\mathrm{\Omega }}_r$ using the distance matrix $\mathrm{\Delta }$. Calculate a temporary label for each child node $i$ by summing the permanent label of parent node $j$ from vector ${\mathrm{\Pi }}_r$ and the length of the link $i\to j:{\mathrm{\Delta }}_{ij}$.
• Node Selection: Select the node with the smallest temporary label and add it to the end of the set ${\mathrm{\Omega }}_r$, removing it from ${\mathrm{\Gamma }}_r$. Add the corresponding parent node $j$ to the end of the set ${\mathrm{\Phi }}_r$ and the corresponding temporary label to ${\mathrm{\Pi }}_r$. With the updated ${\mathrm{\Omega }}_r$, repeat steps 2 and 3 until there are no elements left in ${\mathrm{\Gamma }}_r$.

To obtain the length of the shortest path from origin node $r$ to any other node in the network, find the position of the destination node in ${\mathrm{\Omega }}_r$ and read the corresponding element in ${\mathrm{\Pi }}_r$. To obtain the shortest path itself, find the position of the destination node $s$ in ${\mathrm{\Omega }}_r$, read the element in the same position in ${\mathrm{\Phi }}_r$, and repeat the process until node $r$ is reached in ${\mathrm{\Phi }}_r$ (i.e., trace the shortest path backward until the origin is reached). The links 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 performed for a single origin node $r$, 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 $G$.

Further details of the algorithm can be found in .