Safety: relaxation never sets dist[v] below $\delta(s,v)$ ⇒ any final value = weight of a real
path. Every algorithm in this chapter is just "relax edges in some order."
Order of relaxation = the whole difference between the algorithms.
The three algorithms
Algorithm
Solves
Neg. edges?
Neg.-cycle detect?
Time
Space
Strategy
Dijkstra
SSSP
❌ no
❌ no
$O(E\log V)$
$O(V)$
greedy: extract-min unfinalized, relax its out-edges
Bellman-Ford
SSSP
✅ yes
✅ yes
$O(VE)$
$O(V)$
relax ALL edges $|V|-1$ times, + 1 detector pass
Floyd-Warshall
APSP
✅ yes
✅ (neg. diagonal)
$\Theta(V^3)$
$\Theta(V^2)$
DP over allowed waypoints; k loop outermost
Dijkstra skeleton
dist[s]=0, all others $\infty$; push (0,s).
Pop min (d,u); if d>dist[u] skip (stale). Else relax every out-edge of u, pushing improved (dist[v],v).
dist holds $\delta(s,\cdot)$; prev gives the shortest-path tree.
- Lazy deletion: push duplicates on improvement; skip stale pops with if d>dist[u]: continue.
Bellman-Ford skeleton
dist[s]=0, others $\infty$.
Repeat $|V|-1$ times: relax every edge.
One more pass: any edge still relaxable ⇒ negative cycle reachable ⇒ return "undefined".
Floyd-Warshall recurrence
$$D_{k+1}[i][j]=\min\big(D_k[i][j],\ D_k[i][k]+D_k[k][j]\big),\qquad D_0[i][j]=w(i,j),\ D_0[i][i]=0.$$
Negative $D[i][i]$ after completion ⇒ negative cycle through $i$.
"When to use what" decision aid
Situation
Use
One source, non-negative weights (distances, times, costs)
Dijkstra
One source, negative edges possible
Bellman-Ford
Need to detect a negative cycle / arbitrage
Bellman-Ford (detector pass)
All pairs, dense graph, small–medium $V$
Floyd-Warshall
All pairs, sparse graph
Dijkstra from every vertex ($O(VE\log V)$)
Unit weights only (every edge = 1)
BFS (Ch. 28), $O(V+E)$ — Dijkstra is overkill
Single source→target on a map, want speed
A* (Dijkstra + admissible heuristic)
Why Dijkstra is correct (the proof in one frame)
Invariant: when a vertex $u$ is finalized, dist[u] $=\delta(s,u)$ already.
Proof shape: contradiction. Let $u$ = first vertex finalized with dist[u] $>\delta(s,u)$. On a
true shortest path to $u$, let $y$ = first unfinalized vertex, $x$ its (finalized) predecessor. Then:
$\text{dist}[y] = \delta(s,y)$ (relaxing $(x,y)$ when $x$ finalized; prefix is shortest)
$\delta(s,y) \le \delta(s,u)$ ← only step using $w \ge 0$
$\text{dist}[u] \le \text{dist}[y]$ (greedy chose $u$ over $y$)
🚪 Threshold: a greedy algorithm can be provably optimal — find the invariant the greedy choice
preserves (reused for MST cut property, Ch. 32).
Why Bellman-Ford's $|V|-1$: a shortest path with no negative cycle is simple (≤ $|V|-1$ edges);
path-relaxation property — after $k$ passes, all $\le k$-edge shortest distances are exact.
Common pitfalls
Pitfall
Reality
Finalize a vertex on discovery (first finite dist)
Only safe to finalize the global min unfinalized vertex
Run Dijkstra with negative edges
Wrong answers — greedy commits before seeing a cheaper negative route. Use Bellman-Ford
"Add a constant to remove negatives, then Dijkstra"
Penalizes paths by edge count; can change which path is shortest. Wrong
Shortest = fewest edges
No — shortest = minimum total weight; BFS solves only the unit-weight case
Floyd-Warshall with i or j outside k
Wrong; k (waypoint) must be the outermost loop
Forget the detector pass in Bellman-Ford
Silently returns garbage on a negative cycle
Drop if d > dist[u]: continue in heap Dijkstra
Still correct, but reprocesses stale entries (slower)