Worked examples — Floyd-Warshall — all-pairs shortest paths, O(V³)

Two symbols we will use constantly, defined now so nothing is assumed:

---

The scenario matrix

Every graph you feed Floyd-Warshall lands in one or more of these boxes. Below the table, each row gets its own fully worked example.

#	Case class	What makes it tricky	Example
A	All-positive edges	The "easy" baseline; a detour beats a direct edge	Ex 1
B	A helpful negative edge	Detour becomes cheaper than the direct edge (Dijkstra breaks here)	Ex 2
C	Unreachable pair	$d[i][j]$ stays $\infty$ forever; must not relax through it	Ex 3
D	Chained improvement	Unlocking a later $k$ builds on a previous $k$'s work — proves loop order	Ex 4
E	Negative cycle	"Shortest" is undefined; diagonal goes negative	Ex 5
F	Tie / degenerate (self-loop, zero weight, equal routes)	min picks one; self-loop must not corrupt	Ex 6
G	Real-world word problem	Translate "cheapest flight" into a matrix	Ex 7
H	Exam twist: wrong loop order	Same graph, broken code — see the actual wrong number	Ex 8

We will use small graphs so you can check every number by hand.

---

Case A — all-positive edges (baseline)

1. Base matrix. $d[0][1]=3,d[0][2]=10,d[1][2]=4$, diagonal $=0$, everything else $\cdot$. Why this step? Floyd-Warshall must start from the direct-edge picture ($k=0$, no midpoints allowed).
2. Unlock $k=0$. Nothing points into $0$, so $d[i][0]=\cdot$ for $i\ne 0$ and no relaxation fires. Why this step? $d[i][0]+d[0][j]$ is $\cdot +\text{something}=\cdot$, never smaller.
3. Unlock $k=1$. Check $d[0][2]$ vs $d[0][1]+d[1][2]=3+4=7<10$. Relax: $d[0][2]\leftarrow 7$. Why this step? Now vertex $1$ is a legal midpoint, so route $0\to 1\to 2$ is finally on the table.
4. Unlock $k=2$. $2$ has no outgoing edges, so no path can pass through it. No change.

Verify: the only two routes $0\to 2$ are direct ($10$) and via $1$ ($7$). $\min (10,7)=7$. ✔

---

Case B — a helpful negative edge

1. Base: $d[0][1]=4,d[0][2]=5,d[1][2]=-3$.
2. Unlock $k=1$. $d[0][2]$ vs $d[0][1]+d[1][2]=4+(-3)=1<5$. Relax: $d[0][2]\leftarrow 1$. Why this step? min does not care about the sign of an edge — it just adds and compares. A negative edge simply makes some sums smaller, which is exactly what a shortest-path algorithm wants.
3. Other unlocks change nothing.

Verify: routes $0\to 2$: direct $5$, via $1$: $4-3=1$. $\min (5,1)=1$. ✔

---

Case C — an unreachable pair

1. Base: $d[2][0]=\cdot$ (no edge), and $2$ has no outgoing edge at all.
2. Through every unlock $k=0,1,2$: to relax $d[2][0]$ we would need $d[2][k]+d[k][0]$ to be finite. But $d[2][k]=\cdot$ for every $k$ (nothing leaves $2$). So the sum stays $\cdot$. Why this step? This is the guardrail. If you use a huge finite sentinel instead of true $\infty$, be careful: $\text{HUGE}+\text{HUGE}$ can overflow or look "cheaper" than another HUGE. Use a value like $10^{18}$ and either skip relaxation when either term is the sentinel, or keep the sentinel far below overflow.

Verify: $2$ has out-degree $0$, so $d[2][0]$ is unreachable $\Rightarrow$ stays $\infty$. ✔

---

Case D — chained improvement (why later $k$ builds on earlier $k$)

1. Base: $d[0][1]=d[1][2]=d[2][3]=1$, $d[0][3]=10$.
2. Unlock $k=1$. $d[0][2]\leftarrow d[0][1]+d[1][2]=2$. Now $0\to 2$ costs $2$ using midpoint $\{1\}$. Why this step? This half-built value ($0\to 2=2$) is exactly what the next unlock will reuse.
3. Unlock $k=2$. $d[0][3]\leftarrow \min (10,d[0][2]+d[2][3])=\min (10,2+1)=3$. Why this step? Here is the payoff: because step 2 already made $d[0][2]=2$, unlocking $2$ now reaches all the way to $3$. A later $k$ stood on the shoulders of an earlier $k$. This is precisely why $k$ must be the outer loop — the parent note's rule made concrete.

Verify: shortest $0\to 3$ is the 3-edge chain $=3$, beating direct $10$. $\min (10,3)=3$. ✔ This is Dynamic Programming in action: the answer for $\{1,2\}$ is assembled from the answer for $\{1\}$.

---

Case E — a negative cycle

1. Base: diagonal all $0$; $d[0][1]=1,d[1][2]=-1,d[2][0]=-1$.
2. Unlock $k=1$. $d[0][2]\leftarrow d[0][1]+d[1][2]=1-1=0$.
3. Unlock $k=2$. $d[0][0]\leftarrow \min (0,d[0][2]+d[2][0])=\min (0,0-1)=-1$. Why this step? The diagonal entry $d[0][0]$ starts at $0$ ("stand still, cost nothing"). The only way it drops below $0$ is a genuine cheaper-than-standing-still loop back to $0$ — i.e. a negative cycle.
4. Test: scan the diagonal. $d[0][0]=-1<0$ $\Rightarrow$ negative cycle reported.

Verify: cycle weight $=1+(-1)+(-1)=-1$, and it pushes $d[0][0]$ to $-1<0$. ✔ When this happens, all shortest-path outputs on that cycle are meaningless (you can loop to $-\infty$). If you must handle negative cycles cleanly across a graph, that's where Johnson's Algorithm and reweighting come in.

---

Case F — degenerate: self-loop, zero weight, and a tie

1. Base: $d[0][0]$ — careful! We initialize the diagonal to $0$ (standing still is free), which is $\le 5$, so we keep $d[0][0]=0$, not the self-loop weight $5$. Why this step? The DP defines $d(i,i)=0$. A positive self-loop can never beat standing still, so we ignore it. (A negative self-loop, however, would be a length-1 negative cycle — caught by Case E's test.)
2. Unlock $k=0$. Check $d[0][1]$ vs $d[0][0]+d[0][1]=0+0=0$. Tie with current $0$; min keeps $0$. No harm. Why this step? This is the exact spot the parent note called "the in-place trick": we read $d[0][k]$ and $d[k][j]$ while overwriting the same matrix. Because $d[k][k]=0$, the values we read don't shift mid-iteration. The self-loop being effectively $0$ is what makes overwriting safe.
3. Tie handling. If two routes give equal distance, < (strict) leaves the first one in place — the answer's value is unaffected; only the reconstructed path may differ.

Verify: $d[0][1]=0$ and $d[0][0]=0$ (self-loop of $+5$ correctly unused). ✔

---

Case G — real-world word problem

1. Base matrix (rows/cols $A,B,C,D=0,1,2,3$):

   from\to	A	B	C	D
   A	0	100	250	400
   B	·	0	100	-50
   C	·	·	0	100
   D	·	·	·	0

2. Unlock $k=B$ (=1). $d[A][C]\leftarrow \min (250,100+100)=200$. Also $d[A][D]\leftarrow \min (400,d[A][B]+d[B][D])=\min (400,100-50)=50$. Why this step? The rebate leg $B\to D=-50$ is a negative edge — Floyd-Warshall uses it without complaint, unlike a naïve greedy pricer.

3. Unlock $k=C$ (=2). $d[A][D]$ vs $d[A][C]+d[C][D]=200+100=300$; not better than $50$. No change.

4. Result: cheapest A\to D = \50$via$A\to B\to D$.

Verify: routes $A\to D$: direct $400$; $A\to B\to D=100-50=50$; $A\to C\to D=250+100=350$; $A\to B\to C\to D=100+100+100=300$. Cheapest $=50$. ✔ (Units: all dollars, consistent.)

---

Case H — exam twist: the wrong loop order

1. What the bug does. With $k$ innermost, for a fixed $(i,j)$ it sweeps all $k$ — but it does this before the pairs it depends on have been fully computed for outer $i,j$. Concretely, when it processes $(i=0,j=3)$, the entry $d[0][2]$ has not yet been improved to $2$ (that improvement lives at pair $(0,2)$, which for this ordering may come after or without the needed chain). Why this step? The DP recurrence requires that all pairs already account for midpoint set $\{1,\dots ,k\}$ before you unlock $k+1$. Only $k$-outermost enforces that global barrier.
2. Trace (k innermost). Processing $(0,3)$: it tries $d[0][k]+d[k][3]$ for $k=0,1,2,3$. At that moment $d[0][2]$ is still $\cdot$ (never relaxed yet, since pair $(0,2)$ hasn't been improved), so $d[0][2]+d[2][3]=\cdot$. And $d[0][1]+d[1][3]=1+\cdot =\cdot$. So $d[0][3]$ stays $10$.
3. Buggy output: $d[0][3]=10$, the direct edge — wrong (correct is $3$).

Verify: correct order gives $3$; the $k$-innermost order on this graph gives $10$. They differ, confirming the bug is real. ✔

---

Recall

Recall Which case is which?

Match each symptom to its case letter. A negative diagonal entry after the run ::: Case E — negative cycle. An entry stubbornly stuck at $\infty$ ::: Case C — unreachable pair. Detour cheaper than the direct edge because of a negative leg ::: Case B (or G) — helpful negative edge. Answer only appears after a second unlock builds on the first ::: Case D — chained improvement, proves $k$-outermost. Wrong answer that equals the raw direct edge ::: Case H — $k$ not outermost. A positive self-loop that must be ignored ::: Case F — degenerate; diagonal stays $0$.