Floyd-Warshall: All-Pairs Shortest Paths in Three Loops
Floyd-Warshall computes shortest paths between every pair of nodes with a triple loop and a distance matrix. Intuition, JavaScript code, walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Dijkstra answers one question: how far is everything from this one source? But sometimes you need the whole grid — the shortest distance from every node to every other node. Run Dijkstra from each vertex and you get there, but it's fiddly and it breaks on negative edges.
Floyd-Warshall does the whole all-pairs table in five lines of real logic: a matrix and three nested loops. No priority queue, no visited set. It's one of the rare algorithms where the code is shorter than the explanation of why it works.
The trick is a single, almost sneaky idea — process intermediate nodes one at a time, in the outermost loop.
The problem
Given a weighted directed graph with V nodes and a list of edges (each [u, v, w] meaning an edge from u to v with weight w), return a V × V matrix where dist[i][j] is the length of the shortest path from node i to node j. Unreachable pairs stay at infinity; a node's distance to itself is 0.
Input: V = 4
edges = [[0,1,4], [0,2,11], [1,2,2], [1,3,10], [2,3,3]]
Output: [ [0, 4, 6, 9 ],
[∞, 0, 2, 5 ],
[∞, ∞, 0, 3 ],
[∞, ∞, ∞, 0 ] ]
// dist[0][2] = 6, not the direct edge 11, because 0 → 1 → 2 costs 4 + 2.
// dist[0][3] = 9, via 0 → 1 → 2 → 3 (4 + 2 + 3), beating the direct 0 → 3 edge weight of ∞.Two facts shape the solution: distances can improve by detouring through other nodes, and negative edge weights are allowed (unlike Dijkstra) — so the algorithm has to be robust to them.
The brute force baseline
The naive reading of "shortest path" is: enumerate every path between each pair and keep the minimum. But the number of simple paths in a dense graph is exponential, so that's hopeless past a handful of nodes.
The realistic baseline is to run a single-source shortest-path search from every vertex:
function allPairsViaDijkstra(V, adj) {
const dist = [];
for (let source = 0; source < V; source++) {
dist[source] = dijkstra(source, V, adj); // one O(E log V) search per node
}
return dist;
}This is O(V · E log V), which is fine — but it has two problems. It's a lot of moving parts to implement correctly V times, and Dijkstra silently returns wrong answers on negative edge weights. To handle negatives you'd swap in Bellman-Ford per source, pushing you to O(V² · E). On a dense graph where E ≈ V², that's O(V⁴).
Floyd-Warshall gets all-pairs shortest paths in O(V³) — better on dense graphs — handles negative edges natively, and detects negative cycles for free. And it fits on a napkin.
The key insight: allow one more intermediate node at a time
Here's the reframe. Define a subproblem: what is the shortest path from i to j if the path is only allowed to pass through intermediate nodes drawn from the set {0, 1, ..., k}?
Start with k = -1: no intermediates allowed, so the only known distances are the direct edges. Now grow the allowed set one node at a time. When you newly permit node k as a waypoint, every shortest path either:
- ignores
k— its value is unchanged from the previous round, or - routes through
k— meaning it goesi → ... → k → ... → j, which splits into the besti-to-kpath plus the bestk-to-jpath, both already computed using nodes{0, ..., k-1}.
So the update is one line:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])The magic is loop order. Because k sits in the outermost loop, by the time you consider routing through k, the values dist[i][k] and dist[k][j] already account for every earlier intermediate node. Each node gets "switched on" as a legal waypoint exactly once, and the whole all-pairs table settles.
The optimal solution
This is exactly the algorithm the Floyd Warshall Algorithm visualizer steps through:
function floydWarshall(V, edges) {
// Initial dist array
const dist = Array.from({ length: V }, (_, i) =>
Array.from({ length: V }, (_, j) => (i === j ? 0 : Infinity))
);
// Fill initial distances from edges
for (let [i, j, w] of edges) {
dist[i][j] = w;
}
// Floyd-Warshall algorithm
for (let k = 0; k < V; k++) {
for (let i = 0; i < V; i++) {
for (let j = 0; j < V; j++) {
dist[i][j] = Math.min(
dist[i][k] + dist[k][j],
dist[i][j]
);
}
}
}
return dist;
}Three lines of setup, three nested loops, one Math.min. The diagonal starts at 0 (zero cost to stand still), direct edges seed the initial "best known" costs, and the triple loop relaxes every pair through every possible waypoint. Infinity + anything stays Infinity in JavaScript, so unreachable legs never masquerade as a cheap detour.
Walkthrough
Trace V = 4, edges = [[0,1,4], [0,2,11], [1,2,2], [1,3,10], [2,3,3]]. After seeding the diagonal and direct edges, the matrix starts as:
to0 to1 to2 to3
fr0 [ 0, 4, 11, ∞ ]
fr1 [ ∞, 0, 2, 10 ]
fr2 [ ∞, ∞, 0, 3 ]
fr3 [ ∞, ∞, ∞, 0 ]Now sweep k from 0 to 3, updating any cell where routing through k is strictly cheaper:
| k (via node) | Cell checked | Old | Detour dist[i][k]+dist[k][j] | New |
|---|---|---|---|---|
| 0 | — | — | nothing reaches node 0, so no i → 0 → j helps | no change |
| 1 | dist[0][2] | 11 | dist[0][1] + dist[1][2] = 4 + 2 = 6 | 6 |
| 1 | dist[0][3] | ∞ | dist[0][1] + dist[1][3] = 4 + 10 = 14 | 14 |
| 2 | dist[0][3] | 14 | dist[0][2] + dist[2][3] = 6 + 3 = 9 | 9 |
| 2 | dist[1][3] | 10 | dist[1][2] + dist[2][3] = 2 + 3 = 5 | 5 |
| 3 | — | — | node 3 has no outgoing edges | no change |
The k = 2 row is the payoff. When we relax dist[0][3] through node 2, we use dist[0][2] = 6 — a value that was itself improved back at k = 1. That chaining is only correct because k is the outer loop: node 1 was fully absorbed before node 2 was ever considered. Final matrix:
to0 to1 to2 to3
fr0 [ 0, 4, 6, 9 ]
fr1 [ ∞, 0, 2, 5 ]
fr2 [ ∞, ∞, 0, 3 ]
fr3 [ ∞, ∞, ∞, 0 ]Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(V³) | three nested loops of size V, each doing constant min work — V·V·V cell evaluations |
| Space | O(V²) | the distance matrix holds one entry per ordered pair of nodes |
| Best case | O(V³) | no early exit — every cell is examined for every k, even if nothing improves |
For 4 nodes that's 4³ = 64 cell evaluations; the visualizer prints exactly that count when it finishes. Note O(V³) beats the O(V²·E) of running Bellman-Ford per source on dense graphs.
Common mistakes
- Wrong loop order.
kmust be the outermost loop. Puttingiorjoutsidekbreaks the invariant thatdist[i][k]anddist[k][j]are already finalized for waypoints belowk, and you get answers that are too large. - Forgetting the diagonal. If
dist[i][i]isn't seeded to 0, no path can "start" correctly and everything downstream inflates. - Overflow from infinity. In languages using a large sentinel like
Integer.MAX_VALUEinstead of a true infinity,dist[i][k] + dist[k][j]can overflow and wrap negative, faking a shortcut. JavaScript'sInfinitysidesteps this, but guard the sum in typed languages. - Assuming Dijkstra's rules apply. Floyd-Warshall welcomes negative edges. To detect a negative cycle, check the diagonal after the loops — if any
dist[i][i] < 0, nodeisits on a cycle whose total weight is negative, and no shortest path is well-defined. - Reusing the matrix across runs. The relaxations mutate
distin place. Rebuild it from the edges on every call, or stale values from a previous graph leak in.
Where this pattern shows up next
Floyd-Warshall is the matrix-DP corner of graph problems. These siblings cover the rest of the graph toolkit:
- Find if Path Exists in Graph — the reachability question, the unweighted cousin of "is
dist[i][j]finite?" - All Paths From Source to Target — DFS enumeration of every route, the exponential brute force this algorithm sidesteps.
- Max Area of Island — grid flood-fill, where connectivity replaces weighted distance.
- Redundant Connection — union-find on edges, another way to reason about how nodes connect.
You can also step through Floyd-Warshall interactively to watch the matrix relax one k-wave at a time.
FAQ
Why does the k loop have to be the outermost one?
Because the correctness proof depends on it. When you relax dist[i][j] through node k, you rely on dist[i][k] and dist[k][j] already being the shortest paths that use only intermediate nodes {0, ..., k-1}. Keeping k outermost guarantees an entire pass over all (i, j) pairs finishes for each waypoint before the next waypoint is enabled. Swap the order and those two sub-distances may not be finalized yet, producing paths that are longer than optimal.
Can Floyd-Warshall handle negative edge weights?
Yes, and that's a headline feature — it's why you'd choose it over running Dijkstra from every source. The min-relaxation makes no assumptions about weight signs. The only thing it can't tolerate is a negative cycle, because then "shortest path" is undefined (you could loop forever getting cheaper). You detect one by checking whether any diagonal entry dist[i][i] dropped below 0 after the loops finish.
When should I use Floyd-Warshall instead of Dijkstra?
Use Floyd-Warshall when you need shortest paths between all pairs of nodes and the graph is reasonably small or dense — its O(V³) cost is independent of edge count, so a near-complete graph doesn't hurt it. Reach for Dijkstra when you only need shortest paths from one source and edge weights are non-negative; a single O(E log V) run is far cheaper than filling an entire V × V matrix.
What is the time and space complexity of Floyd-Warshall?
Time is O(V³) from the three nested loops over the vertex count, each doing constant work. Space is O(V²) for the distance matrix. Crucially, both bounds depend only on the number of vertices, not the number of edges — so on dense graphs it outperforms the O(V²·E) alternative of running Bellman-Ford from every source.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.