1. One-Liner
Floyd-Warshall computes shortest paths between every pair of vertices by allowing intermediate vertices 0..k one at a time in three nested loops.
2. The Problem It Solves
All-pairs shortest paths (APSP) on a directed graph (typically V ≤ 500–1000 in contests). Handles negative edges; reports negative cycles via diagonal.
3. The Core Idea
DP: dist[i][j] = shortest path from i to j using only {0..k-1} as intermediates. When adding vertex k, either ignore k or route through k: min(dist[i][j], dist[i][k]+dist[k][j]).
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Initialize dist[i][j]=w(i,j) or ∞, dist[i][i]=0 |
| 2 | For k from 0 to V−1 |
| 3 | For each i,j: dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]) |
| 4 | If dist[i][i] < 0 for some i → negative cycle |
5. Dry Run Example
Triangle: 0→1 (3), 1→2 (4), 0→2 (10). After k=0,1: path 0→1→2 may improve 0→2 to 7 < 10.
6. Key Properties
| Property | Value |
|---|---|
| Negative edges | Yes |
| Dense vs sparse | O(V³) — best when V small or dense |
| Path reconstruction | Keep next[i][j] matrix |
7. Where It Is Used
| Domain | Use |
|---|---|
| Small graphs | Transitive closure variants |
| Transitive closure | Reachability bitsets |
| UC Berkeley / textbooks | Classic APSP teaching |
8. Interview Tips
Know k as outer loop; why that order matters; compare with V× Dijkstra. Follow-up: detect negative cycle.
9. Comparison with Other Algorithms
| Floyd-Warshall | V × Dijkstra | |
|---|---|---|
| Best for | Small V, dense | Sparse large graphs |
| Neg edges | Yes | Dijkstra fails |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V³) |
| Space | O(V²) |
Implementation Example (PYTHON)
def floyd_warshall(n, dist):
# dist is n x n, dist[i][j] = weight or inf
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist