The RutaBus website wants to publish the table "minimum minutes between any pair of stops": the all-pairs shortest paths problem. Dijkstra (04-05) solves it by sheer repetition — one source at a time —, but there is an algorithm that attacks the whole matrix in one piece, tolerates negative weights, and fits in five lines: Floyd-Warshall. It is the promise we signed in 03-03: dynamic programming on graphs — an ingenious subproblem ("shortest path using only the first k stops as intermediates"), a table that gets filled in, and the solution that emerges once it is complete. In this lesson we will implement it and trace it matrix by matrix, learn to detect negative cycles by looking at a diagonal and to reconstruct paths with a second matrix; and, since this is the module's last stop, we will close with the complete map of the six classics and the bridge to optimization.
Contents
- The all-pairs problem: repeat Dijkstra or something better?
- The dynamic programming idea: permitted intermediates
- Representation: from dictionary to adjacency matrix
- Implementation: three loops and one inequality
- Matrix-by-matrix trace over a 4-stop network
- Negative cycles: the telltale diagonal
- Complexity and path reconstruction
- Module closing: the six classics in one table
The all-pairs problem: repeat Dijkstra or something better?
The obvious option: run dijkstra(network, origin) with each of the V stops as the origin. It is perfectly legitimate — and sometimes the best. Let's compare costs (V stops, E segments):
| Dijkstra × V | Floyd-Warshall | |
|---|---|---|
| Time | O(V · (V+E) · log V) | O(V³) |
| On a sparse graph (E ≈ V) | ≈ O(V² log V) ← wins | O(V³) |
| On a dense graph (E ≈ V²) | ≈ O(V³ log V) | O(V³) ← wins |
| Negative weights? | No (04-05) | Yes (without negative cycles) |
| Code | Heap, stale entries, V runs | Three loops and an if |
| Space | O(V²) to store the result | O(V²) |
Practical reading: for RutaBus's urban network (sparse, positive weights), repeated Dijkstra is asymptotically better. Floyd-Warshall wins when the graph is dense, when there are negative weights (where Dijkstra is not even in the game), or when V is moderate (some 400 stops → 400³ = 6.4·10⁷ dirt-simple operations: milliseconds) and bug-proof code is valued. As always since 02-03: there is no champion, there is context.
The dynamic programming idea: permitted intermediates
Applying dynamic programming (03-03) requires finding the right subproblem. Floyd-Warshall's is a brilliant idea. We number the stops 0, 1, ..., V−1 and define:
D_k[i][j] = cost of the shortest path from
itojusing as intermediate stops only those in the list {0, 1, ..., k−1}.
- Base case, D_0: with no intermediates permitted, only direct segments count — the adjacency matrix as is.
- Recursive step: when we authorize a new intermediate, stop k, every path i→j has two exhaustive and mutually exclusive options: either it does not use k (and then its cost is still D_k[i][j]) or it uses k exactly once — it goes from i to k and from k to j, both legs without using k as an intermediate, that is, D_k[i][k] + D_k[k][j]. The minimum of the two:
- Final answer: D_V, with every stop authorized as an intermediate: the unrestricted shortest path.
It is the signature of dynamic programming from 03-03, point by point: overlapping subproblems (the D_k[i][k] values are reused across the whole row of updates), optimal substructure (the best path via k is composed of two best partial paths), and bottom-up tabulation (from D_0 to D_V). Where min_cost_tab advanced stop by stop along the L2, here we advance permit by permit: each iteration of k does not explore paths, it authorizes a waypoint and lets the table recombine.
Representation: from dictionary to adjacency matrix
The adjacency dictionary of 03-04/04-05 is ideal for iterating over neighbors; Floyd-Warshall, on the other hand, queries and updates arbitrary (i, j) pairs nonstop, so the adjacency matrix suits it: a V×V table where cell [i][j] holds the weight of the direct segment i→j (∞ if it does not exist, 0 on the diagonal).
| Adjacency dictionary (04-05) | Adjacency matrix (here) | |
|---|---|---|
| Space | O(V + E): only what exists | O(V²): every cell, existing or not |
| Is there a segment i→j? | Look up in network[i] |
O(1): read the cell |
| Iterate over i's neighbors | O(degree): direct | O(V): sweep the whole row |
| Ideal for | Sparse graphs, Dijkstra, BFS | Dense graphs, "all pairs" algorithms |
Let's take the 4-stop subnetwork from 03-04 with the minutes from 04-05 — indices 0 = Main Square, 1 = North Station, 2 = Central Hospital, 3 = River Park:
INF = float("inf")
# MS NS CH RP
D = [
[ 0, 4, INF, 2], # Main Square
[ 4, 0, 5, INF], # North Station
[ INF, 5, 0, 8], # Central Hospital
[ 2, INF, 8, 0], # River Park
]The matrix is symmetric because the graph is undirected; with one-way segments it would stop being symmetric and nothing else would change.
Implementation: three loops and one inequality
def floyd_warshall(D):
"""Takes the adjacency matrix; returns the matrix of minimum distances."""
n = len(D)
dist = [row[:] for row in D] # copy: don't stomp on the input
for k in range(n): # intermediate being AUTHORIZED
for i in range(n): # origin
for j in range(n): # destination
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j] # better via k
return distThe inner update is the relaxation from 04-05 in different clothes: "does going from i to j through k improve what I have?". Important details:
- The loop order is not negotiable: k must be the outer one. Each iteration of k completes the transition D_k → D_{k+1} for the whole matrix; putting k inside breaks the subproblem's definition and produces incorrect distances (it is the classic bug of this algorithm).
- Shouldn't D_k and D_{k+1} be kept in separate matrices? Surprisingly, no: during iteration k, the cells
dist[i][k]anddist[k][j]do not change (improving via k a path that starts or ends at k would pass through k twice, and that never helps without negative cycles), so updating the matrix in place is safe. An O(V²) saving at zero cost — a gift that the tabulation of 03-03 does not always hand out. - The initial copy (
[row[:] for row in D]) avoids the classic nested-list aliasing:dist = Dwould copy nothing, anddist = D[:]would copy the outer list but share the rows.
Matrix-by-matrix trace over a 4-stop network
Let's run it on the matrix above, showing the matrix after each value of k. Changes in bold.
k = 0 (Main Square is authorized as an intermediate). Which pairs improve by going through MS? NS↔RP: 4 + 2 = 6 < ∞. Nothing else (the rest already have a better direct segment or involve MS as an endpoint):
| D₁ | MS | NS | CH | RP |
|---|---|---|---|---|
| MS | 0 | 4 | ∞ | 2 |
| NS | 4 | 0 | 5 | 6 |
| CH | ∞ | 5 | 0 | 8 |
| RP | 2 | 6 | 8 | 0 |
k = 1 (North Station is authorized). MS↔CH: 4 + 5 = 9 < ∞ ✔. RP↔CH via NS: 6 + 5 = 11, does not improve the direct 8 ✘:
| D₂ | MS | NS | CH | RP |
|---|---|---|---|---|
| MS | 0 | 4 | 9 | 2 |
| NS | 4 | 0 | 5 | 6 |
| CH | 9 | 5 | 0 | 8 |
| RP | 2 | 6 | 8 | 0 |
k = 2 (Central Hospital) and k = 3 (River Park). Every cell is checked and... nothing improves: for example MS→RP via CH would cost 9 + 8 = 17 against the direct 2, and MS→CH via RP would cost 2 + 8 = 10 against the current 9. D₄ = D₂: it is the final matrix.
Cross-check: the Main Square row — 0, 4, 9, 2 — matches exactly what Dijkstra computed from Main Square in 04-05. Two algorithms, two parent strategies, one same truth; running both and comparing is, incidentally, an excellent testing technique.
Look at what happened in the trace: the path MS→CH = 9 (which in Dijkstra required discovering 10 and correcting to 9) here simply appeared when the right intermediate was authorized (NS, at k = 1). Floyd-Warshall does not explore paths: it lets the table compose them.
Negative cycles: the telltale diagonal
Floyd-Warshall accepts negative weights — the relaxation "settles" nothing irrevocably, so the argument that felled Dijkstra (04-05) does not touch it. Its limit is a different one: cycles of negative total cost. If there exists a cycle whose weights sum to < 0, looping around it reduces the cost indefinitely and "the shortest path" ceases to exist (it tends to −∞).
The elegant part is how it is detected: when the algorithm finishes, just look at the diagonal. dist[i][i] starts at 0 (going from i to i without moving); if the algorithm finds dist[i][i] < 0, there is a path from i to i with negative cost — a negative cycle reachable from i:
In RutaBus minutes are never negative and this does not apply; but if the weights modeled economic cost with per-segment subsidies, a negative cycle would mean "a circular route that generates infinite money" — an unmistakable sign of corrupt data or a badly posed model, and this one-line check exposes it.
Complexity and path reconstruction
Time: Θ(V³). Three nested loops of V iterations with O(1) work inside — the line-by-line analysis of 02-01 in its purest form. No best or worst cases: the structure of the graph does not change the count (at most it changes how many ifs fire the assignment). For the web table with V = 200 stops: 8·10⁶ operations, trivial. With V = 100,000... 10¹⁵: never. The cube puts the frontier at "thousands of nodes, not hundreds of thousands" — the hierarchy of 01-03 in charge once again.
Space: Θ(V²). The matrix itself (thanks to the in-place update, there is no copy per iteration). It is also the size of the output — the all-pairs table RutaBus wanted to publish — so in this problem the quadratic space is irreducible.
Reconstructing the paths. As with Dijkstra (and as with the knapsack in 03-03), the "how much" is not enough: we need the "which way". The breadcrumb here is a matrix of next stops: nxt[i][j] = first stop to move to on the optimal path from i to j. It is initialized with nxt[i][j] = j for every direct segment, and every time the relaxation improves a path via k, the first step toward j becomes the first step toward k:
def floyd_warshall_with_paths(D):
n = len(D)
dist = [row[:] for row in D]
nxt = [[j if D[i][j] != INF else None for j in range(n)] for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
nxt[i][j] = nxt[i][k] # heading to j starts by heading to k
return dist, nxt
def path(nxt, i, j):
if nxt[i][j] is None:
return [] # no path
route = [i]
while i != j:
i = nxt[i][j] # hop to the next stop
route.append(i)
return route
# path(nxt, 0, 2) → [0, 1, 2]: Main Square → North Station → Central HospitalCompared with Dijkstra's previous dictionary (one breadcrumb per stop, walked backwards), here the matrix stores one breadcrumb per pair and is walked forwards. O(V²) breadcrumbs for O(V²) paths: proportionate.
Module closing: the six classics in one table
Six lessons, six algorithms, and no loose pieces: each classic is the embodiment of a strategy from Module 3, analyzed with the tools of Module 2.
| Algorithm | Parent strategy | Time (worst / average) | Aux. space | When to use it in RutaBus |
|---|---|---|---|---|
| Binary search (04-01) | Divide and conquer (discards a half) | O(log n) | O(1) | Searching the sorted stop catalog |
| Insertion sort (04-02) | Incremental (+ greedy best case on order) | O(n²) / O(n²); O(n) if nearly sorted | O(1) | Small or nearly sorted boards; online streams |
| Merge sort (04-03) | Divide and conquer (work when combining) | O(n log n) guaranteed | O(n) | Huge histories, external sorting, stability |
| Quicksort (04-04) | Divide and conquer (work when dividing) | O(n²) / O(n log n) | O(log n) | General in-memory sorting (with a tamed pivot) |
| Dijkstra (04-05) | Greedy (the one that is optimal) | O((V+E) log V) | O(V+E) | Times from one stop; sparse network, weights ≥ 0 |
| Floyd-Warshall (04-06) | Dynamic programming | Θ(V³) | O(V²) | Complete time matrix; tolerates negative weights |
(The fourth suit from 03-04, backtracking, has no representative here: its territory is problems without exploitable structure, where no "efficient classic" was ever born — that absence is a lesson too.)
Common Mistakes and Tips
- Making k the inner loop. The canonical bug: the code runs, returns a plausible-looking matrix... with incorrect distances (it underestimates routes that need "future" intermediates). k authorizes intermediates and must be the outer loop. Quick test: on our network, if MS→CH does not come out as 9, the loops are wrong.
- Initializing the matrix badly: forgetting the 0s on the diagonal, or using a fake "infinity" like
999999that, added twice, breaks the comparison logic with large weights.float("inf")adds and compares correctly (inf + 5 == inf); use it. And if the data contains duplicate segments, the cell must keep the minimum. - Copying the matrix with aliasing:
dist = Dordist = D[:]share the rows (nested lists), and the algorithm will corrupt the input matrix. The correct copy is row by row:[row[:] for row in D]— a hidden Python cost we already know from 02-01. - Using it out of convenience on huge, sparse graphs: V³ with V = 50,000 is 1.25·10¹⁴ operations. For the national stop network, Dijkstra from each origin (or only from the ones actually queried) is the option; Floyd-Warshall is for moderate V or dense graphs. The table in section 1 is the cheat sheet.
- Tip: verify your Floyd-Warshall by checking one row of its matrix against a Dijkstra from that stop (if the weights are ≥ 0). Two independent implementations that agree are worth more than twenty readings of your own code.
Exercises
Exercise 1
Add to the 4-stop matrix a one-way segment Central Hospital → Main Square of 3 minutes (the matrix stops being symmetric: only D[2][0] = 3 changes). Run the trace for k = 0..3 and give the final matrix. Which pair of stops improves thanks to the new segment, and why doesn't the reverse pair?
Exercise 2
With the dist matrix and the nxt matrix from section 7 over the original 4-stop network: reconstruct step by step path(nxt, 3, 1) (River Park → North Station), stating the nxt value consulted at each hop and verifying that the minutes add up to dist[3][1].
Exercise 3
RutaBus is studying two deployments: (a) the urban network with V = 300 stops and E ≈ 900 segments, full matrix recomputed every night; (b) the metropolitan network with V = 20,000 and E ≈ 60,000, where only 1% of the pairs are actually queried. For each case, choose between Floyd-Warshall and repeated Dijkstra and justify with approximate numbers (use log₂ V ≈ 8 for 300 and ≈ 14 for 20,000).
Solutions
Solution 1
Only the cell D[2][0] = 3 changes (CH→MS); D[0][2] remains ∞ until the intermediates do their job. Trace of changes: with k = 0 (MS): NS→RP = 6 and RP→NS = 6 as in the original network; CH→NS via MS = 3+4 = 7 does not improve the direct 5 ✘; but CH→RP via MS = 3+2 = 5 improves the direct 8 ✔. With k = 1 (NS): MS→CH = 4+5 = 9 ✔; on the other hand RP→CH via NS = 6+5 = 11 does not improve its direct 8 ✘ (mind the asymmetry: CH→RP did drop to 5, but RP→CH stays at 8 — they are different cells). With k = 2 (CH): NS→MS via CH = 5+3 = 8 ✘ (direct 4), RP→MS via CH = 8+3 = 11 ✘ (direct 2). k = 3: no changes. Final matrix:
| MS | NS | CH | RP | |
|---|---|---|---|---|
| MS | 0 | 4 | 9 | 2 |
| NS | 4 | 0 | 5 | 6 |
| CH | 3 | 5 | 0 | 5 |
| RP | 2 | 6 | 8 | 0 |
CH→RP improves (8 → 5, via MS thanks to the CH→MS shortcut). The reverse RP→CH stays at 8: the new segment is one-way and only helps paths heading toward Main Square. In directed graphs, each direction lives its own life.
Solution 2
Over the original network, dist[3][1] = 6 (RP→NS via MS). Initially nxt[3][1] = None... until at k = 0 the improvement via MS assigns nxt[3][1] = nxt[3][0] = 0. Reconstruction of path(nxt, 3, 1): route = [3]; consult nxt[3][1] = 0 → hop to MS, route = [3, 0]; consult nxt[0][1] = 1 (direct segment) → hop to NS, route = [3, 0, 1]. Path: River Park → Main Square → North Station; minutes: 2 + 4 = 6 = dist[3][1] ✔.
Solution 3
(a) V = 300: Floyd-Warshall costs 300³ = 2.7·10⁷ elementary operations — tenths of a second, minimal code, and the output (the 9·10⁴-cell matrix) is exactly what is to be published. Dijkstra × 300 ≈ 300 · (300+900) · 8 ≈ 2.9·10⁶ — also trivial and somewhat smaller, but with more code and no material advantage. Either works; Floyd-Warshall is defensible on simplicity. (b) V = 20,000: Floyd-Warshall would cost 20,000³ = 8·10¹² operations (hours or days) and 4·10⁸ matrix cells (several GB): unviable. Dijkstra from one origin ≈ (20,000 + 60,000) · 14 ≈ 1.1·10⁶; even launching it from the 200 queried origins (the 1%), ≈ 2.2·10⁸: perfectly affordable, and computing only what is queried. Dijkstra on demand, no contest. Moral: the all-pairs table should only materialize when everything is truly needed.
Conclusion
Floyd-Warshall crowns the module by proving that the dynamic programming of 03-03 scales to graphs: the subproblem "shortest path using only the first k stops as intermediates" turns the all-pairs problem into a V×V table that three loops fill in Θ(V³), with in-place updating, negative-cycle detection on the diagonal, and a matrix of next stops to reconstruct any itinerary — all while tolerating the negative weights that were forbidden to Dijkstra, in exchange for a cube that limits its use to networks of moderate size or dense ones. With it the repertoire is complete: binary search and the two great sorts as children of divide and conquer, Dijkstra as the provably optimal greedy and Floyd-Warshall as dynamic programming made matrix — six classics we now know how to implement, trace, analyze by cases and, above all, choose according to the RutaBus problem in front of us. We now know how to choose the right algorithm; Module 5 begins where that choice ends: learning to squeeze its implementation — optimizing the code (05-01), the memory (05-02) and spreading the work across several cores (05-03) — because between a well-chosen algorithm and a fast program there still lies a craft, and that craft is what comes next.