Shortest Path: All Pairs
Floyd–Warshall — every distance in one tableHow far is every town from every other town? Floyd–Warshall keeps one table of distances and improves it by letting each vertex in turn be a stop-over: is i → k → j shorter than the best route we already have from i to j? After every vertex has had its turn, the table holds the shortest distance between all pairs — and a second table lets you read the routes themselves.
- All pairsthe shortest distance between EVERY two vertices
- Stop-over kmay a route pass through vertex k?
- O(V³)three nested loops
- next[ ][ ]remembers each route
- Current
- Looking at
- Done
- On the route
Ready
Edges are written A-B:4 (letters A–F, weights 1–99, up to 12 edges) · Keyboard: ← → step · Space play / pause · R reset
Every operation, in plain steps
These are exactly the steps the visualizer animates.
One table with every distance
Floyd–Warshall keeps a V × V table d[i][j] = the shortest distance found so far from i to j. It starts with the direct edges (∞ when there is none, 0 on the diagonal). Then it lets each vertex k in turn be a possible STOP-OVER: if i → k → j is shorter than the best i → j so far, the table is updated. After every vertex has had its turn, the table holds the shortest distance between EVERY pair. A second table, next[i][j], remembers the first step of each best route so the routes themselves can be read back.
#define INF 1000000000
int d[V][V]; // d[i][j]: shortest distance from i to j found so far
int next[V][V]; // next[i][j]: the first vertex after i on that route
// start: the direct edges
for (i...) for (j...)
d[i][j] = (i == j) ? 0 : weight(i, j); // INF if there is no edge
// then try every vertex k as a stop-over
for (k...) for (i...) for (j...)
if (d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
The idea
- d[i][j] starts as the direct edge i → j (∞ if none, 0 if i = j).
- Allow only vertex A as a stop-over, then A and B, then A, B and C, …
- After step k, d[i][j] is the best route using only the first k vertices as stop-overs.
- After the last vertex, nothing is left to improve: all pairs are done.
One step: stop-over k
- For every pair (i, j) look at three cells.
- Compare d[i][k] + d[k][j] with d[i][j].
- Shorter through k: update d[i][j] (and next[i][j]).
- If d[i][k] or d[k][j] is ∞ there is no route through k: skip.
Reading a route
- next[i][j] = the first vertex after i on the best route to j.
- Start at i, jump to next[i][j], then next[that][j], …
- Stop when you reach j: that is the whole path.
- d[i][j] = ∞ means there is no route at all.
Directed and undirected
- Undirected: every edge fills two cells (d[u][v] and d[v][u]).
- Directed: only d[u][v]; the table need not be symmetric.
- The same three loops work for both.
- Weights here are positive (no negative-cost edges).
All pairs vs one source
- Floyd–Warshall: every pair at once, O(V³).
- Dijkstra from every vertex: V runs of O(V²) — also O(V³).
- Floyd–Warshall is shorter to write: three loops.
- On sparse graphs, V runs of Dijkstra with a heap can be faster.
Where it is used
- Tables of distances between all cities.
- Finding the best meeting point for several people.
- Transitive closure: who can reach whom.
- Small graphs where every answer is needed.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
V = number of vertices. The three nested loops always run V³ times, whatever the number of edges. The table needs V² cells.
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Floyd–Warshall (all pairs) | O(V³) |
O(V³) |
O(V³) |
Grows with n |
| Memory for the distance table | O(V²) |
O(V²) |
O(V²) |
Grows with n |
| Read one path from the result | O(1) |
O(V) |
O(V) |
Grows with n |
All pairs vs single source
| Floyd–Warshall | Dijkstra (once) | Dijkstra from every vertex | |
|---|---|---|---|
| Answers | All pairs | One source to all | All pairs |
| Time | O(V³) | O(V²) (array) | O(V³) (array) |
| Code | Three nested loops | A priority queue / min search | Dijkstra in a loop |
| Negative weights | Fine (no negative cycle) | Not allowed | Not allowed |
| Best for | Small graphs, every answer needed | One start vertex | Large sparse graphs (with a heap) |
The distance table for an unreachable pair
| Value | Meaning |
|---|---|
| 0 | From a vertex to itself |
| A number | The shortest distance found so far (final after the last stop-over) |
| ∞ | No route found (yet) — it stays ∞ if the pair is not connected |
Check your understanding
Answer each question — you will see the explanation straight away.
What is the time complexity of Floyd–Warshall?
Three nested loops over all vertices (k, i, j): V × V × V = V³ steps, whatever the number of edges.
What does the outer loop variable k stand for?
In round k every pair (i, j) is tried via the stop-over k: is i → k → j shorter than what we already have?
Before the loops start, what is d[i][j] when there is no edge from i to j (and i ≠ j)?
No known route yet, so the distance is "infinitely far". The loops may lower it later through a stop-over.
Floyd–Warshall finishes with d[A][C] = ∞. What does that mean?
Every real route lowers ∞ to a number at some point, so ∞ can only remain if no sequence of edges leads from A to C.
How does Floyd–Warshall let you read the actual path, not just its length?
Whenever d[i][j] is improved through k, next[i][j] is set to next[i][k]. Following next[ ][ ] from i reaches j.
A graph has 6 vertices. How many times does the innermost line of Floyd–Warshall run?
V³ = 6 × 6 × 6 = 216 (k, i and j each take 6 values).
When is Floyd–Warshall a good choice?
It answers every pair in one go with very little code, but V³ grows quickly, so it suits small graphs.
In an UNDIRECTED graph, what is true about the finished table?
Every edge works both ways, so the distance from i to j equals the distance from j to i: the table is symmetric.
Graphs quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.