Floyd-Warshall
mediumIs it cheaper to go i→j directly, or i→k→j? Applied for every k, that single question resolves every pair at once - as long as k is the outermost loop.
O(V³)Space O(V²)Saved in this browser - no sign-up, nothing sent anywhere.
How floyd-warshall works
Floyd-Warshall answers every shortest-path question at once with a single comparison applied V³ times: is i to k to j cheaper than the best i to j found so far? Three nested loops, one if statement, and a V by V matrix that starts as the adjacency matrix and ends as all-pairs shortest distances.
The order of the loops is the whole algorithm. With k outermost, the invariant holds that after round k, d[i][j] is the shortest path using only the first k vertices as intermediates. Round by round the permitted set grows by one vertex until every path is allowed. Put k inside and that induction collapses - silently.
It is dynamic programming, not graph traversal: no queue, no visited set, no priority. That makes it O(V³) regardless of edge count, which sounds bad but is a tight, cache-friendly triple loop in practice. It also tolerates negative edges, and reports a negative cycle whenever a diagonal entry d[i][i] drops below zero.
Step by step
- Load the matrix for the 6-node default graph: 0 on the diagonal, edge weights like d[A][B] = 4 where edges exist, infinity elsewhere.
- Round k = A: paths may now route through A. B to D improves from infinity to d[B][A] + d[A][D] = 4 + 2 = 6.
- Round k = B: A to C becomes 4 + 6 = 10, A to E becomes 4 + 3 = 7, C to E becomes 9 - all through B.
- Round k = C gives A and B their first routes to F: A to F becomes 10 + 2 = 12, B to F becomes 6 + 2 = 8.
- Round k = E re-routes through E: A to F drops from 12 to 7 + 4 = 11, B to F from 8 to 7, D to F from 14 to 9.
- After the final round every cell is a true shortest distance, readable in O(1). The diagonal stayed at 0, so no negative cycle exists.
Complexity
| Worst case time | O(V³) |
|---|---|
| Space | O(V²) |
The invariant is 'shortest path using only 0..k as intermediates', which requires k outermost.
Reference implementation
Python
def floyd_warshall(n, edges):
INF = float("inf")
d = [[INF] * n for _ in range(n)]
for i in range(n):
d[i][i] = 0
for u, v, w in edges:
d[u][v] = min(d[u][v], w)
# k MUST be the outermost loop - it is the induction variable
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return dJavaScript
function floydWarshall(n, edges) {
const d = Array.from({ length: n }, (_, i) =>
Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity))
);
for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);
for (let k = 0; k < n; k++) // outermost - this is the invariant
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
return d;
}Worth noticing
k must be the outermost loop
The invariant is 'd[i][j] is the shortest path using only vertices 0..k as intermediates'. Each k iteration extends the permitted set by one vertex. Swap the loops and that induction collapses - the algorithm silently returns wrong answers.
One line of logic, all pairs
Is it cheaper to go i→j directly, or i→k→j? Applied for every k, that single question resolves every pair of vertices at once. There is no queue, no priority, no visited set.
O(V³) time, O(V²) space - and that is fine sometimes
Running Dijkstra from every vertex costs O(V·E log V), which is better on sparse graphs. On dense graphs, or when you simply want the whole matrix, Floyd-Warshall's tight triple loop and perfect cache behaviour often wins in practice.
A negative diagonal means a negative cycle
d[i][i] should stay 0. If it goes below zero, there is a route from i back to i with negative total weight - detected for free, with no extra pass.
Common pitfalls
- Putting k innermost. The loops look interchangeable but are not - k is the induction variable, and reordering returns confidently wrong distances with no crash to warn you.
- Forgetting to zero the diagonal, or to keep the minimum when loading parallel edges. Garbage in the base matrix propagates through all V³ updates.
- Using it at scale. V = 2,000 means 8 billion updates - beyond a few hundred vertices, run Dijkstra from each vertex instead.
- Adding infinity to a weight in fixed-width integers. The sum overflows negative and wins every comparison; guard the infinite d[i][k] case explicitly.
- Ignoring the diagonal afterwards. d[i][i] below zero means a negative cycle, and every distance involving that cycle is meaningless.
Where it is used
- Precomputing latency or distance matrices between all pairs of data centres, routers or map waypoints.
- Transitive closure of a relation - which vertices can reach which - by swapping min-plus for boolean and-or.
- Contest and interview problems with V up to a few hundred, where the six-line implementation wins on speed to write.
- Detecting negative cycles in all-pairs settings, read directly off the diagonal.
Frequently asked questions
What is the time and space complexity of Floyd-Warshall?
O(V³) time - the triple loop runs V times V times V regardless of how many edges exist - and O(V²) space for the distance matrix. On the 6-vertex default that is 216 updates; at V = 500 it is 125 million, still fine; at V = 5,000 it is not.
Why does the k loop have to be outermost?
The invariant is inductive: after processing k, d[i][j] is optimal among paths whose intermediates all come from the first k vertices. Each round extends that set by one. With k inside, the update consults d[i][k] values that were never finalised, and some pairs end up too large.
Floyd-Warshall vs running Dijkstra from every vertex - which is faster?
Dijkstra V times costs O(V·E log V), which wins on sparse graphs and is the standard choice. Floyd-Warshall wins when the graph is dense, when negative edges rule Dijkstra out, or when V is small enough that the short cache-friendly loop is simply the pragmatic answer.
Does Floyd-Warshall handle negative weights?
Negative edges, yes - nothing in the update assumes positivity. Negative cycles, no: distances through them diverge to minus infinity. The tell is a negative diagonal entry, since d[i][i] should stay 0; check for it after the loops finish.