All-Pairs Shortest Paths
In short: Floyd–Warshall fills a full n × n table of cheapest costs
between every pair of stops in three nested loops. The outer loop allows one
more stop, k, as a possible stopover; each cell then takes the smaller of
its current cost or the route through k: dist[i][k] + dist[k][j]. After
all n stops have been allowed as stopovers, every entry is final. It costs
O(n³) time and O(n²) space — worth it exactly when you need every pair,
not just one.
![Three nodes i, k, j: a dashed grey direct edge from i to j labelled dist[i][j] old, and two solid green edges i-to-k and k-to-j, with the formula dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])](/api/assets/dsa/assets/d5a5b32d2f7e6519.png)
Meridian's dispatch desk quotes prices all day: what does it cost to move a pallet from the mill to the harbour? Then the quay to the depot, then the harbour to the mill. Running a search for every quote is wasteful when the network barely changes between morning and night. Better to build one table overnight, every depot to every depot, and turn each quote into a lookup.
That table is the all-pairs shortest paths problem. You could run a search from each depot in turn, but there is a simpler algorithm that fills the whole table at once, handles rebates, and is three nested loops long: Floyd–Warshall.
Growing the set of allowed stopovers
Number the depots 0 to n − 1. Start with a table holding only direct roads: the road's cost where there is one, 0 on the diagonal, infinity elsewhere. Think of that as "the cheapest route with no stopovers allowed".
Now allow depot 0 as a stopover. For each pair (i, j), the best route either avoids
depot 0 (the table has it already) or goes i → 0 → j, costing
dist[i][0] + dist[0][j]. Take the smaller. Then allow depot 1, then 2, and so on.
Once all n are allowed, the table is complete.
Written as a recurrence, with k the newest allowed stopover:
That is dynamic programming again, and the table is the DP table. The whole algorithm is n snapshots of one matrix. Scrub through them for Meridian's four depots. At each stopover, the highlighted row and column are the only cells the pass reads, and the arrows show which two cells each improvement came from:
Floyd–Warshall is n snapshots of one table. Each pass allows one more depot as a stopover, and reads only that depot's row and column.
Stopover depot. Row i, column j is the cheapest cost from i to j. The pass for the depot reads only the depot's row (costs from it) and its column (costs to it). 4 by 4 table. 16 of 16 cells filled.
The quay → mill route (quay → harbour → depot → mill) was only found in the last pass, because it reused harbour → mill from the first. Each pass builds on the finished work of the ones before.
A pass only has to look at row k and column k to decide everything:
inf = float("inf")
dist = [[0, 3, 8, inf], [3, 0, 2, inf], [inf, inf, 0, 1], [4, inf, inf, 0]]
k = 0 # allow only the depot as a stopover
for i in range(4):
for j in range(4):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
print(dist[3][1], dist[3][2])The algorithm
It is exactly as short as promised:
It updates in place, which can't mix old and new values badly: during the pass for k, row k and column k never change (going via k to reach k adds nothing). Rebates are fine as long as no loop makes money.
Step through a three-depot version and watch the one improvement happen:
The loop order is the proof
Three nested loops look interchangeable. They are not. With k innermost, each pair
(i, j) tries every stopover once and is never revisited, reading dist[i][k] and
dist[k][j] before those entries have been improved themselves:
The cheapest depot → mill route costs 2 + 4 + 3 = 9, but this prints inf. Reorder the loops so the table is built stopover by stopover.
Your Floyd–Warshall, drawn
Here's the full algorithm drawing each pass and each improvement. Add a road, say
["quay", "depot", 1], and see which cells get cheaper and in which pass.
Your Floyd–Warshall. Each improvement reads two cells from the current stopover's row and column.
Routes, not just prices, and loops that pay
A quote needs a price; a driver needs a route. Keep a second table, hop[i][j],
holding the first depot after i on the best known route to j. A direct road
sets it to j; when the route via k wins, the first step becomes the first step
towards k:
If a loop of rebates does make money, the table shows it on the diagonal. A depot's cost to itself starts at 0 and only falls if some loop through it is net negative:
inf = float("inf")
# depot -> mill 2, mill -> quay -3, quay -> depot 0: a loop worth -1 per lap
d = [[0, 2, inf], [inf, 0, -3], [0, inf, 0]]
for k in range(3):
for i in range(3):
for j in range(3):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
print(min(d[i][i] for i in range(3)) < 0)Floyd–Warshall or one search per depot?
Floyd–Warshall is always n³. Running Dijkstra from every depot costs about n × (n + E) log n, and which is smaller depends on how many roads there are. On a dense network, with roads between most pairs of depots, E is close to n² and Floyd–Warshall wins outright: it has no heap and tiny constants. On a sparse street map, with a handful of roads per junction, the repeated searches win, and by more as the map grows.
On a street map where each junction has about 3 roads, Floyd–Warshall does n³ steps and n runs of Dijkstra about n × 4n × log₂ n, so Floyd–Warshall does n / (4 log₂ n) times the work:
| junctions n | Floyd–Warshall's work over repeated Dijkstra |
|---|---|
| 50 | 2.2× |
| 100 | 3.8× |
| 340 | 10× |
| 2,000 | 46× |
Below a few hundred nodes Floyd–Warshall's simplicity wins, and dispatch's depot table (dozens of depots) is squarely there. For every junction in a city, run searches instead, and only between the pairs you actually need.
Repeated Dijkstra has one catch: rebates. Johnson's reweighting removes it.
Give every depot a potential h, computed once with Bellman-Ford, and change each
road's cost to cost + h[a] − h[b]. Every new cost is non-negative, and every route
from s to t changes by the same h[s] − h[t], so the cheapest route stays the
cheapest:
Dijkstra on the reweighted roads, then + h[t] − h[s] to undo it, gives true costs.
That makes all-pairs on a big sparse map with rebates cost one Bellman-Ford plus n
Dijkstras.
Interview-style: where to base the night van
Meridian keeps one emergency van overnight. Which depot should it wait at, so that its longest possible drive to any other depot is as short as possible?
Each depot's worst drive is the largest number in its row of the all-pairs table. Build the table once, take each row's maximum, and pick the smallest. A depot that can't reach everyone has infinity in its row, which rules it out automatically. The obvious "centre" of the map is often not the answer, which is exactly why the boss exercise asks you to compute it rather than eyeball it.
What it costs
| Time | Memory | Rebates? | |
|---|---|---|---|
| Floyd–Warshall | O(n³) | O(n²) | yes; money loops show on the diagonal |
| Dijkstra from every node | O(n (n + E) log n) | O(n + E) per run | no |
| Johnson (one Bellman-Ford + n Dijkstras) | O(nE + n (n + E) log n) | O(n + E) per run | yes |
❓ Cross-question — "Is it really the same algorithm for reachability, or the heaviest truck a road can carry?" Yes. Floyd–Warshall only needs a way to join two halves of a route and a way to choose between routes: plus and min for costs, and and or for reachability, min and max for load limits. The drill and capstone exercises swap those two operations and keep the three loops.
Quick practice
inf = float("inf")
dist = [[0, 2, inf], [inf, 0, 3], [1, inf, 0]]
k = 0
for i in range(3):
for j in range(3):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
print(dist[2][1])The depot's cost to itself should be 0, but this prints 6 (the cost of a round trip). Fix how the table is initialised.
🎯 Your turn
Write depot_matrix(depots, roads). depots fixes the row and column order;
roads is a directed list of [from, to, cost] (rebates allowed, no money-making
loops). Return the matrix of cheapest costs, with 0 on the diagonal and None
where there is no route:
depot_matrix(["depot", "mill", "quay"], [["depot", "mill", 3], ["mill", "quay", 2], ["quay", "depot", 4]])→[[0, 3, 5], [6, 0, 2], [4, 7, 0]]
Hint: direct roads first (keep the cheaper of parallel roads), three loops with
k outside, then swap infinity for None.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian's router is built. ✅