Dijkstra's Algorithm

Dijkstra's algorithm solves the single-source shortest path (SSSP) problem on a weighted, directed (or undirected) graph $G = (V, E)$ with a nonnegative weight function $w: E \to \mathbb{R}_{\geq 0}$, and a designated source vertex $s$. For every vertex $v$, the goal is to compute $\delta(s, v)$, the weight of the shortest path from $s$ to $v$ (or $\infty$ if $v$ is unreachable). The algorithm maintains, for every vertex $v$, a tentative distance estimate $d[v]$, initialized to $\infty$ (except $d[s] = 0$), and a predecessor pointer $\pi[v]$ used to reconstruct the actual path. As in basic Edge Relaxation and Optimal Substructure, the core primitive is the relax operation on an edge $(u,v)$ with weight $w(u,v)$: if $d[u] + w(u,v) < d[v]$, we set $d[v] \leftarrow d[u] + w(u,v)$ and $\pi[v] \leftarrow u$. What Dijkstra's algorithm adds is a disciplined order in which to perform relaxations, guaranteeing that each vertex is relaxed from correctly-computed neighbors and processed exactly once. The algorithm partitions vertices into a finalized set $S$ (whose shortest distances are known to be exact) and the rest. It repeatedly selects the vertex $u \notin S$ with the smallest tentative distance $d[u]$, adds it to $S$, and relaxes all edges leaving $u$. Because $S$ only grows and each vertex enters $S$ with its true shortest distance already locked in, the process resembles a wavefront expanding outward from $s$ in order of increasing distance — closest vertices are settled first.

Step-by-step mechanism: 1. Initialize $d[s] = 0$ and $d[v] = \infty$ for all other $v$; set $\pi[v] = \text{nil}$ for all $v$. 2. Insert all vertices into a min-priority queue keyed by $d[\cdot]$. 3. While the priority queue is nonempty: a. Extract the vertex $u$ with minimum $d[u]$ (this is the "finalize" step). b. For each edge $(u, v)$ leaving $u$, relax it: if $d[u] + w(u,v) < d[v]$, update $d[v]$ and $\pi[v]$, and update $v$'s priority in the queue (a decrease-key operation). 4. When the queue is empty, every reachable vertex has its correct shortest distance in $d[\cdot]$, and the shortest-path tree is encoded by $\pi[\cdot]$. A key implementation detail: many practical implementations use a lazy priority queue that allows duplicate entries rather than true decrease-key, checking a `visited`/`finalized` flag to skip stale entries. This trades a slightly larger queue for simpler code, without changing the asymptotic bound when using a binary heap. ``` function DIJKSTRA(Graph G, weight w, source s): for each vertex v in G.V: d[v] = INFINITY pi[v] = NIL finalized[v] = false d[s] = 0 Q = new MinPriorityQueue() // keyed by d[v] Q.insert(s, priority = 0) while Q is not empty: u = Q.extract_min() // vertex with smallest d[u] if finalized[u]: continue // stale entry (lazy deletion) finalized[u] = true for each edge (u, v) with weight w(u, v) in G.adj[u]: if finalized[v]: continue newDist = d[u] + w(u, v) if newDist < d[v]: d[v] = newDist pi[v] = u Q.insert(v, priority = newDist) // "lazy" decrease-key return d, pi ``` To reconstruct the actual shortest path to a vertex $t$, follow $\pi[t], \pi[\pi[t]], \dots$ back to $s$ and reverse the sequence.

Time complexity. The algorithm performs exactly $|V|$ extract-min operations (each vertex is finalized once) and up to $|E|$ decrease-key/insert operations (once per edge relaxation that improves a distance). With a binary heap, extract-min costs $O(\log V)$ and each insert/decrease-key costs $O(\log V)$, giving

With a Fibonacci heap, extract-min is $O(\log V)$ amortized but decrease-key is $O(1)$ amortized, giving the asymptotically better

which matters for dense graphs ($E = \Theta(V^2)$), where it beats the binary-heap bound. In practice, binary heaps (or even a simple array-based $O(V^2)$ implementation for dense graphs) are often faster in wall-clock time due to lower constant factors and better cache behavior, illustrating a classic asymptotics-versus-constants tradeoff.

Space complexity is $O(V + E)$: adjacency-list storage plus arrays for $d$, $\pi$, and the priority queue's contents.

Correctness proof (invariant argument). The central claim is: > Invariant. At the moment a vertex $u$ is extracted from the priority queue (finalized), $d[u] = \delta(s, u)$, the true shortest-path distance. Proof by induction on the order of extraction. Let $u_1, u_2, \dots$ be the order in which vertices are finalized, with $d[u_1] \le d[u_2] \le \cdots$ (this ordering holds by definition of extract-min). Base case: $u_1 = s$, and $d[s] = 0 = \delta(s,s)$, correct since all weights are nonnegative (no negative cycle can make a shorter path). Inductive step: Suppose $d[u_i] = \delta(s, u_i)$ for all $i < k$. Consider $u_k$, about to be extracted. Suppose for contradiction that $d[u_k] > \delta(s, u_k)$. Take the true shortest path $P$ from $s$ to $u_k$. Since $s$ is finalized and $u_k$ is not yet finalized, $P$ must cross from the finalized set to the unfinalized set at some edge $(x, y)$, where $x$ is already finalized (so $d[x] = \delta(s,x)$ by the inductive hypothesis) and $y$ is not yet finalized. Because all edge weights are nonnegative, the prefix of $P$ up to $y$ is itself a shortest path, so

But $x$ was finalized before $u_k$, so at the time $x$ was processed the edge $(x,y)$ was relaxed, giving $d[y] \le d[x] + w(x,y) = \delta(s,y) \le \delta(s,u_k) < d[u_k]$. Then $y$ would have a smaller tentative distance than $u_k$ and would have been extracted before or at the same time as $u_k$ — contradicting the assumption that $u_k$ was chosen as the next minimum. Hence no such crossing point can give a strictly shorter path, and $d[u_k] = \delta(s, u_k)$. $\blacksquare$ The nonnegativity of weights is essential here: it is what guarantees the prefix of a shortest path is itself shortest, and what prevents a later relaxation through an unfinalized vertex from ever undercutting an already-finalized distance. This is precisely why the algorithm fails on graphs with negative edges — the invariant's crossing-edge argument collapses, since a longer detour through a very negative edge could beat a currently "shortest" finalized value.

Tradeoffs. Dijkstra's algorithm assumes weights are known upfront and nonnegative; it does not handle negative edges (use Bellman-Ford Algorithm) and is not directly parallelizable in its classic sequential form due to the strict extraction order, though bucket-based and parallel variants (e.g., Δ-stepping) relax this at the cost of extra bookkeeping.

Consider the graph from the diagram: vertices $\{A, B, C, D, E, F\}$, source $A$, edges $A{-}B{:}4$, $A{-}C{:}1$, $B{-}D{:}3$, $B{-}E{:}7$, $C{-}E{:}2$, $D{-}F{:}6$, $E{-}F{:}3$.

Final distances: $d[A]=0,\ d[B]=4,\ d[C]=1,\ d[D]=7,\ d[E]=3,\ d[F]=6$. Notice at step 5, $F$ is extracted with $d[F] = 6$ even though $D$ (with $d[D]=7$) has not yet been finalized — this is exactly the invariant in action: since $6 < 7$, and all weights are nonnegative, no path through the still-open $D$ could possibly produce a shorter route to $F$, so $F$'s distance is safely locked at 6. Reconstructing the path to $F$: $\pi[F] = E$, $\pi[E] = C$, $\pi[C] = A$, giving path $A \to C \to E \to F$ with total weight $1+2+3=6$, matching $d[F]$.

Internet routing protocols such as OSPF (Open Shortest Path First) run a Dijkstra computation on each router's local view of the network topology to determine the next hop for every destination. GPS and mapping systems (road networks with travel-time weights) use Dijkstra's algorithm or heavily optimized descendants like contraction hierarchies and A search, which augment Dijkstra with a heuristic to prune the search space while preserving the same correctness guarantee. Robotics and game AI use it (or its generalization A) for pathfinding on grids and navigation meshes. Dependency and build systems occasionally reduce ordering problems to shortest-path computations when costs represent resource usage. It also serves as the direct algorithmic ancestor discussed when introducing the All-Pairs Shortest Paths Overview, since running Dijkstra's algorithm from every vertex is one standard way to solve the all-pairs problem on graphs with nonnegative weights.

Ask the tutor: How does the choice of priority queue implementation change Dijkstra's algorithm's performance on very dense versus very sparse graphs?