Skip to main content

Floyd-Warshall and DP Shortest Paths

What This Concept Is​

Floyd-Warshall solves all-pairs shortest paths (APSP) on a directed graph with arbitrary real weights and no negative cycles, in O(|V|^3) time and O(|V|^2) space.

The idea is dynamic programming over "intermediate vertices." Let d^{(k)}[i][j] be the shortest distance from i to j using only vertices {1, ..., k} as intermediate. The recurrence is:

d^{(0)}[i][j] = w(i, j)   if (i, j) in E
              = 0         if i = j
              = +infinity otherwise

d^{(k)}[i][j] = min( d^{(k-1)}[i][j],
                    d^{(k-1)}[i][k] + d^{(k-1)}[k][j] )

The algorithm implements this with a triple loop; the space can be collapsed to a single |V| x |V| matrix updated in place:

for k in 1..|V|:
    for i in 1..|V|:
        for j in 1..|V|:
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] := dist[i][k] + dist[k][j]
                next[i][j] := next[i][k]

Negative cycles appear as dist[i][i] < 0 after completion.

Floyd-Warshall belongs to the broader family of matrix-DP shortest paths. Reusing the same scaffold:

  • Replace (min, +) with (or, and) and you get Warshall's transitive-closure algorithm.
  • Replace with (min, max) and you get bottleneck shortest paths between every pair.
  • Replace with (+, *) on probabilities and you get highest-probability paths.
  • CLRS 23.1 presents the "slow" O(|V|^3 log |V|) matrix-multiplication version that repeatedly squares a distance matrix; Floyd-Warshall is a faster relative.

Why It Matters Here​

Floyd-Warshall is the shortest-path algorithm you reach for when:

  • you need all-pairs distances and the graph is dense or small-ish (a few hundred to low thousands of vertices)
  • the graph might have negative edges but no negative cycles
  • the implementation simplicity (30 lines with a matrix) is worth more than shaving a factor

It is also a canonical example of DP on graphs, teaches the "vertex-as-intermediate" subproblem pattern, and exposes the semiring generalization - same code, different (op, op) pair, different answer.

Concrete Example​

Consider the directed graph with |V| = 4:

Initial matrix d^{(0)}:

         1    2    3    4
    1  [ 0    3    inf  7 ]
    2  [ 8    0    2    inf]
    3  [ 5    inf  0    1 ]
    4  [ 2    inf  inf  0 ]

After k = 1 (allow 1 as intermediate): d[2][4] = min(inf, 8+7) = 15, d[3][2] stays, d[4][2] = min(inf, 2+3) = 5. Others unchanged.

After k = 2: d[1][3] = min(inf, 3+2) = 5, d[4][3] = min(inf, 5+2) = 7. Others relax accordingly.

After k = 3: d[1][4] = min(7, 5+1) = 6, d[2][4] = min(15, 2+1) = 3, d[4][4] = min(0, 7+1) = 0 (no negative cycle).

After k = 4: pairs using 4 as intermediate further tighten: d[2][1] = min(8, 3+2) = 5, d[3][1] = min(5, 1+2) = 3, etc.

Final matrix shows shortest distances between every ordered pair.

Path reconstruction uses the next[i][j] table populated alongside dist: path(i, j) = i, next[i][j], next[next[i][j]][j], ..., j.

Common Confusion / Misconceptions​

  • "Outer loop is over passes." No. The outer loop is over k (intermediate vertex), and the recurrence structure requires k outermost. Swapping with i or j silently breaks correctness because d^{(k)} needs d^{(k-1)} values; the in-place update works only because d[i][k] and d[k][j] are invariant across the (i, j) sweep at fixed k.
  • "Floyd-Warshall needs a strongly connected graph." It does not. Unreachable pairs stay at +infinity.
  • "It cannot handle negative edges." It can, as long as no negative cycle exists. Negative cycles appear as dist[i][i] < 0 for some i on the diagonal after completion.
  • "|V|^3 is always slow." For |V| <= 400, Floyd-Warshall fits in under a second in most languages and has excellent cache locality. The constant factor is tiny compared to any priority-queue Dijkstra.
  • "Johnson's is strictly better for APSP." Johnson's is asymptotically better for sparse graphs (O(|V||E| + |V|^2 log |V|)), but has a larger constant and requires Bellman-Ford preprocessing. For dense |V| = 300 graphs, Floyd-Warshall wins in wall-clock time.

How To Use It​

Use Floyd-Warshall when:

  • APSP is needed,
  • |V| is small enough that |V|^3 is acceptable (|V| <= ~1000 on modern hardware, often less for tight loops in higher-level languages),
  • weights may be real-valued (negative edges fine, negative cycles not).

If the graph is sparse and |V| is large, prefer Johnson's algorithm: one Bellman-Ford reweighting plus |V| Dijkstra runs for O(|V||E| + |V|^2 log |V|).

Implementation tips:

  • lay out dist as a flat |V| * |V| array in row-major order for cache locality
  • use an explicit sentinel (e.g., INT_MAX / 2 to avoid overflow in the sum) for +infinity
  • check dist[i][i] < 0 after the triple loop to flag negative cycles
  • populate a next[i][j] matrix alongside for O(|V|) path queries

Transfer / Where This Shows Up Later​

  • S3 (systems). Transitive closure (Warshall) answers "can process A ever influence process B?" in capability-analysis tools.
  • S4 (compilers). Reaching-definitions and available-expressions analyses use Warshall-style iterative closure over the CFG.
  • S5 (OS). Deadlock avoidance: the safety algorithm for the Banker's analysis is transitive-closure-like.
  • S6 (databases). Recursive CTE (WITH RECURSIVE) implements transitive closure; graph databases expose APSP via Floyd-Warshall or Johnson's.
  • S7 (DDD). Cross-context cost analysis at small scales uses APSP on the context map.
  • S8 (distributed). Latency matrices between regions are often cached as APSP outputs recomputed periodically.

Back-link to M5 dynamic programming - Floyd-Warshall is the canonical introduction to DP over graphs. Back-link also to concept 09 for when APSP is the right variant.

Check Yourself​

  1. Why does the outer loop run over k (intermediate vertex), not over iterations?
  2. How do you reconstruct shortest paths, not just distances, in O(|V|) per query?
  3. How do you detect a negative cycle with Floyd-Warshall?
  4. When is Johnson's algorithm asymptotically faster than Floyd-Warshall?
  5. Generalize the recurrence to compute transitive closure (Warshall). What (op, op) pair do you use?
  6. Why does the in-place update (single matrix) still produce correct d^{(k)} values, despite overwriting the d^{(k-1)} array as it goes?

Mini Drill or Application​

Run Floyd-Warshall on:

1 -(3)-> 2
2 -(-2)-> 3
3 -(2)-> 1
1 -(7)-> 3

Produce the final dist[][] and path-reconstruction table next[][]. Note whether a negative cycle is present.

Implementation drill.

  1. Implement Floyd-Warshall in a tight triple loop with a flat array and verify it matches repeated Dijkstra on a small test graph.
  2. Extend to return next[][] and reconstruct paths.
  3. Add negative-cycle detection via the diagonal.
  4. Implement Warshall's transitive-closure variant with the (or, and) semiring.
  5. Benchmark on |V| = 300, 500, 1000 dense random graphs; plot time vs |V|^3.
  6. Implement Johnson's algorithm and compare wall-clock time vs Floyd-Warshall on a sparse |V| = 500, |E| = 2000 graph with some negative edges.

Read This Only If Stuck​