Floyd's Algorithm: All-Pairs Shortest Paths

Warshall's algorithm answers reachability for every pair. Floyd's algorithm (often Floyd–Warshall) upgrades the same three-loop skeleton to compute shortest distances for every pair:

D[i][j] = the minimum total weight of any path from i to j.

The transformation is one substitution. Where Warshall combines facts with OR / AND:

Floyd combines costs with min / +:

Read it aloud: "the best way from i to j is either what I already know, or going via k — whichever is cheaper."

When do you want all pairs at once? Route-planning tables, computing a graph's diameter, finding the cheapest cycle, or as a preprocessing step when many distance queries follow. And because it never settles anything (unlike Dijkstra), negative edges are fine — only negative cycles are off-limits, and Floyd even detects those.

Exactly like Warshall, define D⁽ᵏ⁾[i][j] = the length of the shortest i → j path whose intermediate vertices all come from {1, …, k}:

• D⁽⁰⁾ = the weight matrix: w(i→j) where an edge exists, 0 on the diagonal, ∞ elsewhere.
• Going from k−1 to k: the best path allowed to use k either skips k (cost D⁽ᵏ⁻¹⁾[i][j]) or passes through it exactly once (cost D⁽ᵏ⁻¹⁾[i][k] + D⁽ᵏ⁻¹⁾[k][j]). Take the minimum.
• D⁽ⁿ⁾ = true shortest distances.

This is dynamic programming on the set of allowed intermediates — the subproblem index is k, not a vertex or a path.

Negative cycle detection: the diagonal starts at D[i][i] = 0. If any D[i][i] ever drops below zero, vertex i lies on a cycle whose total weight is negative — at that point "shortest path" stops being well-defined for pairs that can detour through that cycle.

Run Floyd on a 4-vertex weighted digraph (edges 1→3 (3), 2→1 (2), 3→2 (7), 3→4 (1), 4→1 (6)). Step forward and backward with the ← / → arrow keys or the buttons below.

What to watch:

• For each intermediate k (cyan row/column), every pair (i, j) is asked: is the detour i → k → j cheaper? The two cyan cells are the detour halves D[i][k] and D[k][j]; the amber-ringed cell is the target D[i][j]. Improvements flash green.
• Early ∞ entries melt away as detours appear: D[2][3] becomes 2 + 3 = 5 the moment k = 1 lets paths hop through vertex 1.
• At k = 3 the matrix fills in fastest — vertex 3 is the graph's main junction (1→3 and 3→ everything).
• The very last improvement (k = 4) shortens D[3][1] from 9 to 7 via 3 → 4 → 1 — even an already-finite entry can keep improving until the final round.

Identical shape to Warshall — three loops, k outermost — with min/+ in the middle and an ∞-guard so that nonexistent paths don't poison the arithmetic. Path reconstruction needs one extra matrix next[i][j] (the first hop on the best known i → j path), updated whenever a detour wins. The C++ tab runs the visualization's graph and prints the final distance matrix.

The same accounting as Warshall:

• Time: Θ(V³) — three loops, constant work inside, no dependence on E.
• Space: Θ(V²) for the distance matrix (plus another V² for next if you need actual paths). The in-place update is safe: during round k, the cells D[i][k] and D[k][j] cannot themselves improve in that round (a detour through k doesn't shorten a path to k — that would require a negative D[k][k], i.e. a negative cycle).

How it compares for all-pairs distances:

For dense graphs (E ≈ V²) Floyd matches Dijkstra-from-every-vertex while being dramatically simpler — about five lines of code with no data structures. For large sparse graphs with non-negative weights, repeated Dijkstra wins.