Floyd-Warshall

313. Floyd-Warshall

All-pairs shortest path algorithm — finds the shortest distance from every node to every other node in $𝑂 (𝑉^{3})$ .

Useful when you need the distance matrix for many queries, vs running Dijkstra from each source ( $𝑂 (𝑉 (𝑉 + 𝐸) log 𝑉)$ ).

313.1. Algorithm

Dynamic programming. Let $𝑑_{𝑘} (𝑖, 𝑗)$ = shortest path from $𝑖$ to $𝑗$ using only intermediate nodes from ${1, \dots, 𝑘}$ :

𝑑_{𝑘} (𝑖, 𝑗) = min (𝑑_{𝑘 - 1} (𝑖, 𝑗), 𝑑_{𝑘 - 1} (𝑖, 𝑘) + 𝑑_{𝑘 - 1} (𝑘, 𝑗))

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 → $𝑂 (𝑉^{3})$ . Space $𝑂 (𝑉^{2})$ (the matrix). Update in place — no need for separate “old” and “new” matrices.

313.2. Edge cases

Negative edges: handled (unlike Dijkstra)
Negative-cycle detection: after the run, if any $𝐷 [𝑖] [𝑖] < 0$ , the graph has a negative cycle reachable from $𝑖$
Disconnected nodes: stay at $\infty$

313.3. Compared to single-source alternatives

	Floyd-Warshall	$𝑉$ × Dijkstra	$𝑉$ × Bellman-Ford
All-pairs cost	$𝑂 (𝑉^{3})$	$𝑂 (𝑉 (𝑉 + 𝐸) log 𝑉)$	$𝑂 (𝑉^{2} 𝐸)$
Negative edges?	yes	no	yes
Memory	$𝑂 (𝑉^{2})$	$𝑂 (𝑉^{2})$	$𝑂 (𝑉^{2})$
Dense graphs ( $𝐸 \approx 𝑉^{2}$ )	$𝑂 (𝑉^{3})$ — best	$𝑂 (𝑉^{3} log 𝑉)$	$𝑂 (𝑉^{4})$
Sparse graphs ( $𝐸 \approx 𝑉$ )	$𝑂 (𝑉^{3})$	$𝑂 (𝑉^{2} log 𝑉)$ — best	$𝑂 (𝑉^{3})$

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

313.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 $𝜋$ .

313.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 / +

313.6. See also

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