= Dijkstra algorithm
{c}
{title2=$d(v)=\operatorname{dist}(s,v)$}
{wiki=Dijkstra's_algorithm}
= Dijkstra's algorithm
{c}
{synonym}
The <Dijkstra algorithm> solves the single-source <shortest path problem> in a finite <graph> with nonnegative <edge> weights, finding distances to all reachable <vertices>. Start with <tentative distance> $d(A)=0$ and $d(v)=\infty$ elsewhere. Repeatedly choose the unfinalized <vertex> with least <tentative distance>, declare that label permanent, and perform <edge relaxation> on its outgoing <edges>. For an <undirected graph>, inspect both directions. A finite <tentative distance> always records the cost of a discovered <graph path>, but can improve before finalization.
In our example, finalizing $A$ discovers $C$ at $1$, $B$ at $4$, and $D$ at $10$. Choose $C$ next: <edge relaxation> through $C$ lowers $B$ to $1+2=3$ and $D$ to $1+5=6$. Choose $B$: <edge relaxation> through $B$ lowers $D$ to $3+1=4$. Finally choose $D$. The permanent distances are therefore $A:0$, $C:1$, $B:3$, $D:4$; the evolving <tentative distances> were $B:4\to3$ and $D:10\to6\to4$.
\Image[/dijkstra-distance-frontier.png]
{title=<Tentative distances> fall until the <Dijkstra algorithm> makes each label permanent}
Store a <shortest-path predecessor> whenever <edge relaxation> improves a label. The final table contains enough information to reconstruct routes, rather than merely their costs:
|| <Vertex>
|| Distance from $A$
|| <Shortest-path predecessor>
|| Finalization order
| $A$
| $0$
| None: source
| $1$
| $C$
| $1$
| $A$
| $2$
| $B$
| $3$
| $C$
| $3$
| $D$
| $4$
| $B$
| $4$
Following <shortest-path predecessors> backwards gives $D,B,C,A$; reversing the order gives $A,C,B,D$. If only this destination matters, stop when $D$ is finalized. Stopping when $D$ is first discovered would incorrectly return $10$. If the smallest remaining <tentative distance> is $\infty$, all remaining <vertices> are unreachable.
Why is the permanent choice safe? Suppose the selected <vertex> $u$ had a cheaper <graph path>. Let $y$ be the first unfinalized <vertex> on that <graph path>. Its preceding <vertex> was finalized, so <edge relaxation> has already offered $y$ a label no larger than that prefix's cost. Nonnegative remaining <edge> weights make the whole cost at least this prefix's cost; selection gives $d(u)\le d(y)$. A cheaper <graph path> would contradict these comparisons. Zero weights are allowed; ties can be resolved arbitrarily. This is the reason the <label-setting shortest-path algorithm> works, rather than a lucky feature of the drawing.
Negative weights break that reasoning. In a <directed graph> with $s\to u$ costing $2$, $s\to v$ costing $5$, and $v\to u$ costing $-4$, the <Dijkstra algorithm> would finalize $u$ at $2$ before discovering the cheaper cost $1$. The <Bellman-Ford algorithm> handles negative <edge> weights when no relevant negative <directed cycle> exists.
With an <adjacency list> and an indexed <binary heap> implementing a <priority queue>, the <time complexity> is $O((|V|+|E|)\log |V|)$ for $|V|\ge2$, using <Big O notation>. Each <vertex> is extracted at most once, each <edge> is inspected once per direction, and each successful <edge relaxation> decreases a heap key in $O(\log |V|)$ time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses $O(|V|)$ space beyond the <graph>. Simply scanning all remaining <vertices> gives $O(|V|^2+|E|)$ instead.https://algs4.cs.princeton.edu/44sp/DijkstraSP.java.html[Princeton, DijkstraSP implementation]{ref}https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/IndexMinPQ.html[Princeton, indexed binary heap operations]{ref}
The 1959 paper presents the <shortest path problem> as its second problem, after the <minimum spanning tree> problem, and grows known shortest routes in increasing distance order.https://www.cs.yale.edu/homes/lans/readings/routing/dijkstra-routing-1959.pdf[Dijkstra, A note on two problems in connexion with graphs, pp. 269–271]{ref} In his later recollection, Dijkstra dated the shortest-route discovery to 1956: a demonstration for the ARMAC computer used a simplified Dutch railway map and printed the route between towns. A practical request became an enduring <algorithm> because the same distance rule applies to any suitable <graph>.https://garfield.library.upenn.edu/classics1983/A1983QA19900001.pdf[Dijkstra's recollection, published in 1983]{ref}
Back to article page
