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

$d_k(i,j)$ is the length of the ==shortest path from $i$ to $j$ that is allowed to use only the vertices $\{1,2,\dots ,k\}$ as intermediate (middle) stops==. The endpoints $i$ and $j$ are always allowed; only the middle is restricted.

For $k=0$ no middle vertices are allowed, so the only legal path is a single direct edge (or staying put). The complete base case has three cases: $d_0(i,j)=\{\begin{array}{ll}0& i=j(\text{cost of staying put})\\ w(i,j)& \text{edge }i\to j\text{ exists}\\ +\infty & i\ne j\text{ and no edge}\end{array}$ In particular the diagonal starts at $==d_0(i,i)=0==$, which later becomes the key to the negative-cycle test.

No. The intermediate vertex ==k must be the outermost loop==. The dynamic program recurses on $k$: every pair $(i,j)$ must fully account for the set $\{1,\dots ,k\}$ before we unlock $k+1$. With k innermost you read half-updated values and can return wrong distances.

Floyd-Warshall. Dijkstra's Algorithm breaks on negative edges. Bellman-Ford run from every source costs $O(V^{2}E)=O(V^4)$ for a dense graph. Floyd-Warshall gives clean $O(V^3)$ and handles negative edges, provided there are no negative cycles (if a negative cycle exists, "shortest" is undefined — you could loop forever toward $-\infty$ — and the algorithm instead detects it via the diagonal). For $V\le 400$ that is $\approx 6.4\times 10^7$ operations — instant.

Initial matrix ($\cdot =\infty$):

• $k=0$ (unlock vertex 0): nothing points into $0$, so $d[i][0]=\infty$ for $i\ne 0$. No detour through $0$ helps.
• $k=1$ (unlock vertex 1): check $d[0][2]$ vs $d[0][1]+d[1][2]=3+4=7<10$. Update $d[0][2]=7$.
• $k=2$ (unlock vertex 2): $2$ has no outgoing edge, no improvement.

Final $d[0][2]=\boxed{7}$. In the figure, the two-hop route $0\to 1\to 2$ (drawn in amber, weights $3$ then $4$, total $7$) beats the single direct edge $0\to 2$ (drawn in white, weight $10$) — so the detour wins.

• $k=1$ (unlock vertex 1): $d[0][2]$ vs $d[0][1]+d[1][2]=2+(-5)=-3<6$. Update $d[0][2]=-3$.

Final $d[0][2]=\boxed{-3}$. The min operation does not care about the edge sign — it just compares numbers — so a negative edge is handled with zero extra code, unlike Dijkstra's Algorithm which would wrongly commit to $6$.

Initial:

• $k=0$ (unlock vertex 0): $d[2][1]$ vs $d[2][0]+d[0][1]=7+1=8$ → update $d[2][1]=8$. $d[2][2]$ stays $0$.
• $k=1$ (unlock vertex 1): $d[0][2]$ vs $d[0][1]+d[1][2]=1+2=3<100$ → update $d[0][2]=3$. $d[2][2]$ vs $d[2][1]+d[1][2]=8+2=10$ (no, $0$ smaller).
• $k=2$ (unlock vertex 2): now vertex $2$ may be a middle stop. The only pair that improves is $d[1][0]$: check $d[1][2]+d[2][0]=2+7=9<\infty$ → update $d[1][0]=9$. Every other pair is checked but does not improve, because its current value is already $\le$ the "through $2$" candidate: $d[1][1]$ vs $2+8=10$ (keep $0$); $d[0][0]$ vs $3+7=10$ (keep $0$); $d[0][1]$ vs $3+8=11$ (keep $1$). All diagonal entries stay $0$, confirming no negative cycle.

Final:

Cycle total $=2+(-3)+(-1)=-2<0$, so a negative cycle exists.

The proof appears on the diagonal. After the sweep, a path $0\to 1\to 2\to 0$ becomes legal and its length is $-2$: $d[0][0]=\min (0,2+(-3)+(-1))=\min (0,-2)=-2<0.$ Because $d[i][i]$ starts at $0$, only a negative loop back to $i$ can push it below $0$. Negative cycle detected ($d[0][0]=\boxed{-2}$). In the figure, the three edges form a loop with total weight $-2$; after the sweep the self-distance cell $d[0][0]$ (highlighted in amber) reads $-2$ instead of its starting $0$.

If the optimal $i\to j$ path passes through $k$, we cut it at $k$ into $i\to k$ and $k\to j$. Suppose the first piece $i\to k$ revisited $k$. Then it would contain a cycle from $k$ back to $k$. With no negative cycles, any cycle has length $\ge 0$, so removing it cannot make the path longer — the optimal choice never includes it. Hence the first half uses $k$ only as its endpoint, and its intermediate vertices lie in $\{1,\dots ,k-1\}$. That is precisely the previous subproblem $d_{k-1}(i,k)$, so the recursion closes on itself. This is the Dynamic Programming "optimal substructure" property.

The entries we read, $d[i][k]$ and $d[k][j]$, are exactly the ones that touch vertex $k$ as an endpoint. In iteration $k$ they could only change to $d[i][k]\leftarrow \min (d[i][k],d[i][k]+d[k][k]).$ But $d[k][k]=0$ (no negative cycle), so $d[i][k]+d[k][k]=d[i][k]$ — unchanged. Same for $d[k][j]$. The values we read are stable throughout the $k$-pass, so a single $V\times V$ matrix is correct.

Initialise next:

• diagonal: next[0][0]=0, next[1][1]=1, next[2][2]=2;
• edges: next[0][1]=1, next[1][2]=2, next[0][2]=2, next[2][0]=0;
• non-edges (unreachable so far): next[1][0]=None, next[2][1]=None.

This None marks "no known route yet" — if a pair stays None after the algorithm, no path exists, so reconstruction returns "unreachable".

When $k=0$ relaxes $d[2][1]$ (via $2\to 0\to 1$), set next[2][1]=next[2][0]=0. When $k=1$ relaxes $d[0][2]$ (via $0\to 1\to 2$), set next[0][2]=next[0][1]=1.

Rebuild $0\to 2$: start at $0$. next[0][2]=1 → go to $1$. next[1][2]=2 → go to $2$. Reached destination. Path $=\boxed{0\to 1\to 2}$, total weight $1+2=3$. ✔

Replace min(+) with OR(AND):

reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

Meaning: $i$ reaches $j$ if it already did, or if $i$ reaches $k$ and $k$ reaches $j$. This is Warshall's algorithm — same $O(V^3)$ skeleton.

Apply: reach[0][1]=T, reach[1][2]=T. Under $k=1$: reach[0][2] = F or (reach[0][1] and reach[1][2]) = T and T = True. So yes, $0$ reaches $2$. $\boxed{\text{True}}$

Johnson's Algorithm. It uses Bellman-Ford once to compute a potential $h(v)$, reweights each edge $w^{\prime }(u,v)=w(u,v)+h(u)-h(v)\ge 0$, then runs Dijkstra's Algorithm from every vertex on the non-negative graph. Complexity $O(VE+V\cdot E\log V)=O(VE\log V)$ — far better than $O(V^3)$ when $E\ll V^2$ (sparse). For sparse negative-edge graphs, Johnson wins; for dense small graphs, Floyd-Warshall wins.

The three loops each run over all $V$ vertices, independently, so the inner line runs $V\cdot V\cdot V=V^3$ times. For $V=5$: $5^3=\boxed{125}$. This is why the complexity is exactly $\Theta (V^3)$ — no early exits, every triple $(k,i,j)$ is visited once.

Swap the operations: outer combine over the two path choices becomes max, and the "join two halves" becomes min (a path is only as wide as its narrowest edge):

w[i][j] = max( w[i][j], min(w[i][k], w[k][j]) )

This is Floyd-Warshall over the (max, min) semiring — the skeleton is identical.

Apply: direct $0\to 2$ gives bottleneck $3$. Via $k=1$: $\min (w[0][1],w[1][2])=\min (6,4)=4$. Take $\max (3,4)=4$. Widest $0\to 2$ bottleneck $=\boxed{4}$ (route $0\to 1\to 2$, narrowest edge $=4$).

• Warshall: $V^3=2000^3=8\times 10^9$.
• BFS from every source: $V\cdot (V+E)=2000\cdot (2000+4000)=2000\cdot 6000=1.2\times 10^7$.

BFS-from-every-source is faster by a factor of $\frac{8\times 10^9}{1.2\times 10^7}\approx \boxed{667}$. Lesson: the $O(V^3)$ triple loop is only "the king" for dense graphs and small $V$; on sparse graphs the per-source BFS/Dijkstra family wins by orders of magnitude.

1. Why is k outermost? ::: The DP recurses on $k$; each pair must finish accounting for $\{1,\dots ,k\}$ before unlocking $k+1$.
2. What proves a negative cycle? ::: Some $d[i][i]<0$ after the sweep.
3. Why is the in-place single matrix safe? ::: $d[k][k]=0$ keeps $d[i][k]$ and $d[k][j]$ unchanged during pass $k$.
4. When should you NOT use Floyd-Warshall? ::: Sparse graphs — prefer Johnson's Algorithm or per-source BFS/Dijkstra.