Don't memorize Floyd–Warshall — watch the distance matrix improve. Three nested loops let every vertex take a turn as a stepping stone, one at a time. Each turn asks a single question for every pair: is going i → k → j cheaper than the best route we knew? Answer it for all vertices and the matrix fills with every shortest path at once, in O(V³).
dist[i][j] = cheapest cost from i to j found so far. Starts as the raw edges.
INTERMEDIATE k
The vertex we now allow paths to pass through. The outer loop adds one k at a time.
RELAX
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) — try the detour through k.
ALL-PAIRS
After every vertex has been an intermediate, each cell is the true shortest path.
floyd.sim — 4 vertices, directed weighted edges
Ready
Top is a directed weighted graph; below is its distance matrix. Cell (i,j) starts at the direct edge cost, or ∞ if there is no direct road. Press Step to let each vertex become an intermediate and watch the shortcuts appear.
The trick is dynamic programming. Number the vertices 0..V−1 and ask a smaller question: what is the shortest path from i to j that is allowed to pass only through vertices numbered below some limit k? Start with the limit at zero — no intermediates allowed — so the answer is just the direct edge. Then raise the limit one vertex at a time. When you newly permit vertex k, the only paths that could improve are the ones that go through k, and the best such path is dist[i][k] + dist[k][j] using the answers you already have. That is why k sits on the outer loop.
01
Seed with the edges
dist[i][j] = weight of edge i→j, dist[i][i] = 0, and ∞ where no edge exists.
02
Add one intermediate at a time
Outer loop over k. Now paths may hop through vertex k in addition to everything allowed before.
03
Relax every pair
Inner loops over i, j: if dist[i][k] + dist[k][j] < dist[i][j], the detour through k is cheaper — take it.
04
Order is the whole proof
k outermost guarantees dist[i][k] and dist[k][j] already use only earlier intermediates, so combining them is safe.
Time
O(V³)
Space
O(V²)
Negatives
OK
Output
All pairs
Three flat loops, one matrix, no priority queue — Floyd–Warshall is the shortest correct all-pairs code you can write, and it quietly handles negative edges too. It only breaks on a negative cycle, which you can spot afterward: if any diagonal entry dist[i][i] has gone negative, a cycle around i keeps getting cheaper. For single-source paths on a big sparse graph, reach for Dijkstra instead; for all pairs on a small dense one, this is the tool.
Check yourself
1 · Why does the intermediate vertex k go on the outer loop?
The outer k loop is the DP order: when k is added, the two halves of the detour are already optimal over vertices below k, so combining them is correct.
2 · What does one relaxation actually test?
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) — take the detour through k only if it beats what we knew.
3 · How does Floyd–Warshall handle negative weights?
Unlike Dijkstra, it works with negative edges. A negative cycle makes shortest paths undefined; detect it when a diagonal entry turns negative.
SOLVE IT YOURSELF
Solve it: all-pairs shortest paths
Three nested loops, and every shortest path in the graph falls out. Write it in Python or TypeScript, running for real in your browser. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Hints are below, and Reveal solution is one click away.
YOUR TASK
Implement shortest_paths(n, edges): given n vertices (0…n-1) and a list of directed[u, v, w] edges, return an n × n matrix where entry [i][j] is the shortest distance from i to j — 0 on the diagonal, and infinity where no path exists.
HINTS — 5 IDEAS
Start with dist[i][j] = ∞ everywhere, then dist[i][i] = 0 — a vertex reaches itself for free.
Lay in each edge: dist[u][v] = min(dist[u][v], w). The min matters — a graph may list the same pair twice.
The key loop order is k outermost: "using only vertices 0…k as intermediates, what is the best i→j?"
Relax: if dist[i][k] + dist[k][j] < dist[i][j], you found a better route through k — take it.
Getting k inner instead of outer is the classic bug: it silently returns wrong answers on some graphs, not all.
CPython · WebAssembly✓ Solved
1
1
Questions
Floyd–Warshall vs running Dijkstra from every vertex?
Both give all-pairs shortest paths. Floyd–Warshall is O(V³) with tiny constants and trivial code, ideal for small or dense graphs and it allows negative edges. Dijkstra-from-each-source is roughly O(V·E log V), which wins on large sparse graphs — but only with non-negative weights.
How do I reconstruct the actual path, not just the cost?
Keep a second matrix next[i][j] = the first vertex on the path. Initialise it to j for each edge, and whenever a relaxation through k succeeds, set next[i][j] = next[i][k]. Follow next[i][j] to walk the path.
How do I detect a negative cycle?
Run the algorithm, then scan the diagonal. If any dist[i][i] is negative, vertex i sits on a cycle whose total weight is below zero, so no finite shortest path exists for pairs that can reach it.
Every pair, one triple loop.
Let each vertex be a stepping stone in turn, relax every pair, and the whole matrix settles into the shortest paths — O(V³), negatives welcome.