Warshall & Floyd

How to read this

• Warshall: R(k)[i, j] = 1 means there is a path from i to j whose intermediate vertices are all among the first k. R(0) is the adjacency matrix; R(n) is the transitive closure.
• Floyd: D(k)[i, j] is the length of the shortest path from i to j using only vertices 1..k in between. D(0) is the weight matrix (∞ = no edge); D(n) is the distance matrix.
• During pass k the purple row k and column k never change, so every other cell can be updated from them: a 0 turns into 1 when both R[i, k] and R[k, j] are 1; a distance shrinks when D[i, k] + D[k, j] is smaller.
• In the graph, dashed yellow arrows show the detour i → k → j that the update uses; the red dashed arrow is the new (or shorter) connection i ⇢ j.
• The strip below the stage keeps every matrix of the sequence, so you can compare R(k − 1) with R(k).

Try this

1. Run Warshall on the Levitin digraph (a→b, b→d, d→a, d→c). Only three passes change anything. Which one, and why does pass c do nothing? (c has no outgoing edges.)
2. Switch to Floyd on the Levitin digraph. Check D(4): row a should read 0, 10, 3, 4 and the entry D[c, a] should drop from 9 to 7 in the last pass.
3. Use the path finder: the shortest path from b to d is b → a → c → d of length 6.
4. Set “every cell” and watch the counter: n³ checks no matter what the graph looks like (64 for n = 4). That is why both algorithms are Θ(n³).
5. Turn on 🤔 Predict. At the start of each pass, click the cells you expect to change. Hint: only rows with a 1 (or a finite value) in column k and columns with a 1 in row k can change.