310. Floyd-Warshall

All-pairs shortest path algorithm — finds the shortest distance from every node to every other node in .

Useful when you need the distance matrix for many queries, vs running Dijkstra from each source ().

310.1. Algorithm

Dynamic programming. Let = shortest path from to using only intermediate nodes from :

Either use node as a stop (split at ) or don’t (same path).

Initialize D[i][j] = edge weight (or ∞ if no edge), D[i][i] = 0
For k = 1, 2, …, V:
    For i = 1, …, V:
        For j = 1, …, V:
            D[i][j] ← min(D[i][j], D[i][k] + D[k][j])
Return D

Three nested loops → . Space (the matrix). Update in place — no need for separate “old” and “new” matrices.

310.2. Edge cases

• Negative edges: handled (unlike Dijkstra)
• Negative-cycle detection: after the run, if any , the graph has a negative cycle reachable from
• Disconnected nodes: stay at

310.3. Compared to single-source alternatives

Floyd-Warshall is best for dense graphs with potentially negative edges.

310.4. Path reconstruction

To recover paths (not just distances), maintain a predecessor matrix alongside :

When updating D[i][j] via D[i][k] + D[k][j]:
    π[i][j] ← π[k][j]

Then trace back from to via .

310.5. Applications

• Network routing: distance tables for routing protocols
• Logistics: precompute shipping costs between all warehouses
• Game AI / graph queries: when distance matrix is queried millions of times
• Transitive closure: same algorithm with boolean OR / AND replaces min / +

310.6. See also

• Dijkstra — single-source, non-negative edges
• Dynamic Programming — the framework
• Min Spanning Tree — different problem, related techniques