Floyd-Warshall answers every “how far is node i from node j?” question at once, with three nested loops. Instead of running Dijkstra from every node (expensive for dense graphs), it builds a V × V distance matrix and incrementally allows each vertex to act as an intermediate hop.

It is the canonical example of dynamic programming over a growing set of allowed intermediates — and it gracefully handles negative weights, as long as no negative cycle exists.

How It Works

1. Initialize: dist[i][j] = 0 when i == j, the edge weight when an edge exists, ∞ otherwise.
2. For each intermediate k: for every pair (i, j), set dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
3. After all k rounds, dist[i][j] is the true shortest distance from i to j.

Key Insight

The outer loop defines the DP state: after round k, dist[i][j] is the shortest path from i to j using only intermediate vertices from {0 … k}.

Each round either keeps the best-known path or routes through the new vertex k — a pure optimal-substructure decision. Because the state never needs more than the previous round’s matrix, a single in-place matrix suffices.

Three nested loops over V vertices = O(V³) — acceptable when V is a few hundred and you need the whole matrix anyway.

Worked Example

Consider the visualizer’s weighted graph (S, A, B, C, D, E, T). After initialization, the matrix holds direct edges: S→A=2, S→B=4, A→C=3, A→D=7, B→D=1, C→E=2, D→E=3, D→T=6, E→T=1, diagonal 0, everything else ∞.

Round k = B is a classic improvement: D = B→D + ... — specifically the pair (A, D) improves from 7 to dist[A][B] + dist[B][D] = 4 + 1 = 5 (A→B doesn’t exist, but through later intermediates it will). As each intermediate is “allowed,” watch the matrix cells drop from ∞ to finite and then shrink toward their true values. After all 7 rounds, dist[S][T] = 8 — matching Dijkstra’s answer from the earlier topic.

Handling Negative Weights

Unlike Dijkstra, Floyd-Warshall accepts negative edges — provided there’s no negative cycle. A negative cycle would let paths shrink without bound.

Detection is the algorithm’s final pass:

1. Initialize the diagonal to 0.
2. Run the three nested loops.
3. Scan the diagonal: any dist[i][i] < 0 means i sits on a negative-weight cycle.

Every node on that cycle also shows a negative diagonal entry, so you can find the cycle by chasing the next matrix around i. This same scan proves the “no negative cycles” precondition for Dijkstra-based problems: if any dist[i][i] < 0 shows up, the graph isn’t valid for shortest-path work at all.

Transitive Closure: Reachability as a Boolean FW

A close cousin of shortest paths is reachability: can you get from i to j at all, ignoring weights? Floyd-Warshall becomes a boolean algorithm by swapping the min/+ semiring for OR/AND:

reach[i][j]   = true if edge i→j (or i == j)
reach[i][j]  |= reach[i][k] AND reach[k][j]   for each intermediate k

After all rounds, reach[i][j] is true exactly when j is reachable from i. This is Warshall’s algorithm — Floyd’s namesake — and it runs in the same O(V³) time. It’s the standard way to answer “is the graph strongly connected?”, “which pairs share a connected component?”, or “does the DAG have a path between every ordered pair?” The two algorithms are structurally identical; only the semiring differs. (In the boolean case the matrix can be stored as bitsets, which brings the practical runtime down to O(V³ / word).)

Edge Cases & Pitfalls

• Negative cycles — any dist[i][i] < 0 at the end signals one: the result matrix is meaningless then.
• Unreachable pairs — stay at ∞: report them as unreachable.
• Large graphs — O(V³) time and O(V²) space make it impractical beyond a few hundred vertices. Use single-source algorithms for sparse graphs.
• Path reconstruction — the matrix gives distances only: add a next matrix to recover actual paths.

Comparison: Floyd-Warshall vs Dijkstra-from-every-node

Applications

• Transitive closure — reachability via the boolean semiring (see the dedicated section above)
• Dense or small graphs — when the full matrix is needed and V is manageable
• Shortest cycle & graph diameter — diagonal + max over matrix
• Game-state distances — small state spaces, all pairs

Practice Trajectory

1. Initialize the distance matrix for the visualizer graph by hand.
2. Watch the matrix update as each intermediate is allowed; note which round fixes the longest paths.
3. Compare row S against Dijkstra’s output — they must agree.
4. Detect a negative cycle by checking the diagonal after the final round.
5. Add a next matrix and reconstruct the S→T path.