Chapter 6 · Shortest Paths
Dijkstra's Algorithm
The greedy that works because distances only ever grow — with the proof, the four implementations, and the shapes of problem that are one Dijkstra away.
Given edge weights w: E → ℝ≥ 0 and a source s, compute dist(s, v) for every vertex v — the length of the cheapest walk, where non-negative weights make "cheapest walk" and "cheapest path" the same number. The algorithm is greedy, the proof is two lines of bookkeeping, and the variants (state augmentation) are what contests actually test.
#The algorithm in five lines of intent
- Keep a tentative distance d[v] for every vertex, initially ∞ except d[s] = 0.
- Extract the unprocessed vertex u with minimum d[u].
- u is now settled: d[u] = dist(s,u).
- Relax every edge uv: if d[u] + w(u,v) < d[v], write the better value and push (d[v], v).
- Repeat.
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != d[u]) continue; // stale entry: lazy deletion
if (done[u]) continue;
done[u] = 1;
for (auto [v, w] : g[u]) if (d[u] + w < d[v]) {
d[v] = d[u] + w;
pq.emplace(d[v], v);
}
}If all weights are non-negative, then when u is extracted with d[u] ≠ ∞, d[u] = dist(s,u).
Induct on the extraction order. Invariant: d[v] ≥ dist(s,v) always — true initially (∞), and preserved because every update sets d[v] to the length of an actual path (s ⇝ u optimal, by hypothesis, plus the edge uv). Now suppose u's extraction value were too big: take a shortest path π from s to u; let y be its first vertex not yet settled and x its predecessor on π (settled, since s is settled and u is not). When x was settled, relaxation set d[y] ≤ dist(s,x) + w(x,y) = dist(s,y). Since weights are non-negative, dist(s,y) ≤ dist(s,u) < d[u]. So d[y] < d[u], and y (unsettled) would have been extracted before u — contradiction. ∎
The line dist(s,y) ≤ dist(s,u). If an edge after y on π had negative weight, u could be closer than y, and settling u early would be wrong. This is why Bellman–Ford exists (Bellman–Ford and Negative Weights), and why "Dijkstra with a re-weighting fix" (Johnson potentials) is the honest way to handle negative weights that are known to be acyclic-safe.
#The four implementations, honestly compared
| variant | push | pop | time | when |
|---|---|---|---|---|
| linear scan for min | O(1) | O(n) | O(n2) | dense: m = Θ(n2), n ≤ 5000; no heap code, best constants |
| binary heap + lazy deletion | O(log) | O(log) | O((n+m)log n) | the default, 10 lines |
std::set (decrease-key) | erase+insert | O(log n) | O((n+m)log n) | when you need real decrease-key (fewer stale entries) |
| pairing / Fibonacci heap | O(1) | O(log n) | O(m + nlog n) | theory, and m ≫ n |
| Dial / radix heap | — | — | O(m + nC) / O(m + nlog C) | small integer weights (0-1 BFS, Dial, Potentials, Johnson) |
vector<ll> d(n, INF); vector<char> used(n); d[s] = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int i = 0; i < n; i++) if (!used[i] && (u == -1 || d[i] < d[u])) u = i;
used[u] = 1;
for (int v = 0; v < n; v) if (w[u][v] < INF) d[v] = min(d[v], d[u] + w[u][v]);
}This O(n2) version beats the heap version for n ≤ 2000 on dense graphs and has no stale-entry subtlety — know both.
The same code, seven different answers
- Reconstruct the path: keep
par[v]inside the relaxation; walk back from the target. - Number of shortest paths:
if (d[u]+w == d[v]) ways[v] += ways[u];— but process vertices in settled order, not relaxation order (push(d[v], v)and accumulate when popping, or topologically on the shortest-path DAG). - Second shortest path: state = (vertex, used-or-not one "detour") → run Dijkstra on 2n states.
- Dijkstra with a discount/coupon/special edge: state = (vertex, coupon used) — the "layered graph" idiom (0-1 BFS, Dial, Potentials, Johnson).
- Bounded hops (≤ k edges): dp[hops][v] relaxations = k Bellman-Ford rounds, or Dijkstra with hops in the state.
- Multi-source: push all sources with 0.
- Negative-free all-pairs: run it n times, O(nm + n2 log n) — better than Floyd for sparse graphs (Bellman–Ford and Negative Weights mention in sparse-tricks).
Every extraction, every relaxation and every stale duplicate on this 7-vertex network. Change the source and watch which vertices settle in a different order — but never a different distance.
- Overflow. d[u] + w with d[u] = ∞ overflows
long longif INF isLLONG_MAX. UseINF = 4e18and compare withd[u] + w < d[v]only after checkingd[u] < INF. - Zero-weight edges are fine; negative ones are not — Dijkstra may return a too-small value for some vertices and the correct one for others, which is worse than crashing.
greater<pair<ll,int>>vsless<>: forgetting the comparator gives a max-heap and a wrong order (but sometimes still the right answer by luck — never ship that).- Marking
done[u]at push time instead of pop time breaks the lazy-deletion scheme.