Dijkstra's algorithm

Dijkstra's algorithm finds the shortest path from a given source node to every other node.^{[7]: 196–206} It can also be used to find the shortest path to a specific destination node, by terminating the algorithm once the shortest path to the destination node is known. For example, if the nodes of the graph represent cities, and the costs of edges represent the average distances between pairs of cities connected by a direct road, then Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. A common application of shortest path algorithms is network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and OSPF (Open Shortest Path First). It is also employed as a subroutine in other algorithms such as Johnson's algorithm.


The algorithm uses a min-priority queue data structure for selecting the shortest paths known so far. Before more advanced priority queue structures were discovered, Dijkstra's original algorithm ran in ${\displaystyle \Theta (|V|^{2})}$ time, where ${\displaystyle |V|}$ is the number of nodes.^[8] The idea of this algorithm is also given in Leyzorek et al. 1957. Fredman & Tarjan 1984 proposed using a Fibonacci heap priority queue to optimize the running time complexity to ${\displaystyle \Theta (|E|+|V|\log |V|)}$. This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights. However, specialized cases (such as bounded/integer weights, directed acyclic graphs etc.) can indeed be improved further, as detailed in Specialized variants. Additionally, if preprocessing is allowed, algorithms such as contraction hierarchies can be up to seven orders of magnitude faster.


Dijkstra's algorithm is commonly used on graphs where the edge weights are positive integers or real numbers. It can be generalized to any graph where the edge weights are partially ordered, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing.^[9][10]


In many fields, particularly artificial intelligence, Dijkstra's algorithm or a variant of it is known as uniform cost search and formulated as an instance of the more general idea of best-first search.^[11]

To prove the correctness of Dijkstra's algorithm, we proceed by mathematical induction on the number of visited nodes.^[21]


Invariant hypothesis: For each visited node v, dist[v] is the shortest distance from source to v, and for each unvisited node u, dist[u] is the shortest distance from source to u when traveling via visited nodes only, or infinity if no such path exists. (Note: we do not assume dist[u] is the actual shortest distance for unvisited nodes, while dist[v] is the actual shortest distance)[[


Base case:


The base case is when there is just one visited node, source. Its distance is defined to be zero, which is the shortest distance, since negative weights are not allowed. Hence, the hypothesis holds.


Inductive step:


Assume the hypothesis holds for ${\displaystyle k}$ visited nodes. We wish to show it holds for ${\displaystyle k+1}$ nodes. Let u be the next visited node according to the algorithm, i.e. the node with minimum dist[u]. We claim that dist[u] is the shortest distance from source to u.


To prove this claim, we proceed by contradiction. If there were a shorter path, then this shorter path either contains another unvisited node or not.


For all other visited nodes v, the dist[v] is already known to be the shortest distance from source already, because of the inductive hypothesis, and these values are unchanged.


After processing u, it will still be true that for each unvisited node w, dist[w] will be the shortest distance from source to w using visited nodes only. If there were a shorter path that did not use u, we would have found it previously, and if there were a shorter path using u we would have updated it when processing u.


After all nodes are visited, the shortest path from source to any node v consists only of visited nodes. Therefore, dist[v] is the shortest distance.