All-Pairs Shortest Paths (Floyd-Warshall)
Hard+115 XPFind the cheapest cost between EVERY pair of towns by filling a distance matrix with a triple loop.
No visualization loaded.
Watch
—
Press Run to begin.
Dijkstra answers 'cheapest route from ONE start town to everywhere.' Floyd-Warshall answers a bigger question all at once: 'cheapest route between EVERY pair of towns.' It keeps a grid called dist[i][j] = the best cost found so far from town i to town j (∞ if you can't get there yet). Then it does one elegant thing: it tries each town k, one at a time, as a possible STOPOVER. For every pair (i, j) it asks, 'could I get from i to j cheaper if I'm now allowed to pass through k?' — by comparing dist[i][k] + dist[k][j] with the cost it already had. Allow every town as a stopover in turn, and the grid fills up with all the true shortest distances.
▸What does 'all-pairs' mean, versus single-source?
Single-source (like Dijkstra or Bellman-Ford) gives the cheapest cost from ONE chosen start town to every other town — one row of answers. All-pairs gives the cheapest cost between EVERY pair of towns at once — the whole grid. So Floyd-Warshall hands you dist[i][j] for every i and j in one run.
▸What is the intermediate-node k loop actually doing?
It slowly grows what counts as a 'legal' path. When k=0, you only allow routes that stop over (at most) at town 0. When k=1, you also allow town 1 as a stopover, and so on. Each round the question is the same: 'for this pair (i,j), can I do better by routing THROUGH k?' — i.e. is dist[i][k] + dist[k][j] cheaper than what I had? After every town has had its turn as a stopover, all the best routes have been considered.
▸Why is a MATRIX the natural structure here?
Because the answer itself is a table: a number for every (from, to) pair. dist[i][j] sits in row i, column j. The whole algorithm is just repeatedly improving cells of that grid, and each improvement reads exactly two other cells in the same grid (one in row i column k, one in row k column j). The grid IS the data and the answer.
▸How does it compare to running Dijkstra from every town?
Both can solve all-pairs. Running Dijkstra V times costs about O(V · (V+E) log V). Floyd-Warshall is a flat O(V³) triple loop — often simpler to code and competitive on small or dense graphs, and (unlike plain Dijkstra) it handles negative edges. For big sparse graphs, V Dijkstras can win; for small dense ones, the tidy V³ matrix sweep is hard to beat.
▸Why is the diagonal 0 and missing roads ∞ at the start?
The cost from a town to itself is 0 — you're already there, no road needed, so dist[i][i] = 0. If there's no direct road from i to j yet, you don't know any way there, so it starts at ∞ ('infinitely expensive / unknown'). As stopovers get allowed, those ∞ cells get replaced by real costs whenever a route is finally found.
How the work grows
O(V³) is slow — explodes on big inputs. Three nested loops — k over towns, then i and j over every pair — give V × V × V = V³ cell updates, each O(1). Memory is the V×V matrix itself. It's heavier per-run than one Dijkstra, but it computes EVERY pair's distance in that single sweep.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.