~/home/every vertex a stepping stone: floyd–warshall
Algorithm · Graphs
Every Vertex, A Stepping Stone.
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.
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.