On this page
Description
Sometimes the question isn't "how far is everything from here?" but "how far is everything from everything?" Routing tables, distance matrices and "which city is best connected" all ask that. Floyd-Warshall answers with a triple loop over an n x n matrix. It allows one more waypoint at a time, asking for every pair whether going through that waypoint is shorter. It computes every pair at once and handles negative edges, though not negative cycles. Running a single-source algorithm from every node also works, but for dense graphs this is simpler.
We'll go from simple to more technical:
- The pattern: the triple loop, with the waypoint k outermost.
- A second flavor: questions answered from the finished matrix.
- Where all-pairs tables are used in production.
- What breaks it: the loop order, an infinity that overflows, and graphs too large for O(V^3).
The approach
Java
int[][] floydWarshall(int n, int[][] dist) { // dist[i][j] = direct edge weight, INF if none, 0 on the diagonal
for (int k = 0; k < n; k++) { // waypoint - must be the OUTER loop
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] < INF && dist[k][j] < INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
Python
def floyd_warshall(n: int, dist: list[list[int]]) -> list[list[int]]: # INF where no edge, 0 on the diagonal
for k in range(n): # waypoint - must be the OUTER loop
for i in range(n):
for j in range(n):
if dist[i][k] < INF and dist[k][j] < INF and dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
The invariant: after the outer loop has finished waypoint k, dist[i][j] is the shortest path from i to j that uses only nodes 0..k as intermediate stops. Allowing one more node k either doesn't help, or the best route goes i -> ... -> k -> ... -> j, whose two halves only use nodes 0..k-1 - values the previous iteration already finalized. That's why k must be outermost: with k innermost, dist[i][k] and dist[k][j] are read before they're final, and some pairs are left too long.
A second flavor: questions on top of the matrix
Once every distance is known, many questions are one more scan. "Which city has the fewest other cities within a distance threshold?" counts, per row, the entries at most the threshold:
Java
int best = -1, bestCount = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) if (j != i && dist[i][j] <= threshold) count++;
if (count <= bestCount) { bestCount = count; best = i; } // <= : ties go to the larger index
}
Python
best, best_count = -1, float("inf")
for i in range(n):
count = sum(1 for j in range(n) if j != i and dist[i][j] <= threshold)
if count <= best_count: # <= : ties go to the larger index
best, best_count = i, count
The same matrix answers reachability (is dist[i][j] finite?), graph diameter (the largest finite entry), and negative cycles: after the loops, a negative value on the diagonal means that node can return to itself for a negative total.
Where you'll see it
All-pairs tables appear wherever many point-to-point queries hit a small, fairly static network: precomputed distance matrices for delivery planning and vehicle routing, "how many hops between any two services" in a service mesh, and reachability (transitive closure) in permission systems - Warshall's boolean version asks "can i reach j through k?" instead of "is it shorter?".
Which tool for which job?
| You need | Use |
|---|---|
| All pairs on a small or dense graph | Floyd-Warshall, O(V^3) |
| All pairs on a large sparse graph, weights ≥ 0 | Dijkstra from every node |
| All pairs with negative edges, sparse | Johnson's algorithm |
| The routes, not just the lengths | a next[i][j] first-hop matrix |
| Reachability between all pairs | transitive closure, with bitset rows |
| Negative cycles | a negative diagonal entry; check it after each waypoint |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| k anywhere but the outermost loop | some pairs stay too long, or "no path" | k outermost |
Integer.MAX_VALUE as "no edge" | INF + 5 wraps to -2147483644 | skip infinite halves, or use 10^9 |
| Running it on 10^5 nodes | 10^15 steps and a huge matrix | repeated Dijkstra or BFS |
| Ignoring negative cycles | entries grow without bound | stop at the first negative diagonal entry |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. What does dist[i][j] mean right after the outer loop finishes waypoint k?
Show answer
The shortest path from i to j using only nodes 0..k as intermediate stops. When k reaches n - 1, every node is allowed, so it's the true shortest distance - and each step only needs the finalized values from the previous waypoint.
2. Why is Integer.MAX_VALUE a risky "infinity" here?
Show answer
Adding anything positive to it overflows: Integer.MAX_VALUE + 5 is -2,147,483,644, which looks like an extremely short path and gets written into the matrix. Guard the addition (both halves finite) or choose a sentinel like 10^9, whose double still fits in an int.
3. After running Floyd-Warshall, dist[2][2] is -2. What does that mean?
Show answer
Node 2 can leave and come back for a negative total - it lies on, or can reach and return through, a negative cycle. Shortest distances involving such nodes aren't well-defined, because going around again makes them cheaper.
Key takeaways
- Floyd-Warshall computes all-pairs shortest paths with three nested loops, the waypoint k outermost.
- After waypoint k, dist[i][j] is the best path using only nodes 0..k as stops - the invariant that forces the loop order.
- Guard additions against the infinity sentinel, or pick one whose double still fits.
- A negative diagonal entry reveals a negative cycle; negative edges alone are fine.
- O(V^3) time, O(V^2) space: great for small dense graphs, not for large sparse ones.