The previous lesson ended with a thorn in our side: BFS insists the Hospital is "2 segments" from the Warehouse… via a congested 16-minute avenue, when a 13-minute path exists. When edges have weights, counting segments no longer works: you have to add up minutes. This lesson presents the three classic shortest-path algorithms: Dijkstra (single source, non-negative weights — here we finally cash in the heap seed we planted in 01-04), Bellman-Ford (single source, allows negative weights and detects negative cycles) and Floyd-Warshall (all pairs, pure dynamic programming, direct heir of 01-03). At the end we will build the matrix of real travel times between all of Rutalia's zones — the same kind of matrix that fed the TSP distances in module 2.

1. Why BFS is not enough when edges have weights
2. Dijkstra: the priority queue cashes in its seed
3. Dijkstra's invariant and its complexity
4. Why Dijkstra fails with negative weights
5. Bellman-Ford: relax to exhaustion
6. Negative cycles: when the model breaks
7. Floyd-Warshall: all pairs with dynamic programming
8. Rutalia's travel-time matrix and its connection to the TSP
9. Comparison table and a mention of A*

BFS processes nodes by number of edges from the source, and its correctness depends on "discovered earlier = closer". With weights, that breaks: in the canonical network, ALM→CEN via the direct avenue is 1 edge and 12 minutes, while ALM→MER→CEN is 2 edges and 9 minutes. BFS "closes" CEN at level 1 and never reconsiders.

The conceptual repair is elegant: instead of processing nodes in discovery order (FIFO queue), process them by provisional accumulated distance, always the closest one first. Which structure efficiently hands over "the current minimum" among changing candidates? Exactly the one we studied in 01-04 for prioritizing orders: the binary heap (heapq). Dijkstra is, literally, BFS with the queue swapped for a heap.

Line-by-line breakdown of the important decisions:

• (distance, node) tuples in the heap: heapq orders tuples by their first element, so heappop always returns the node with the smallest provisional distance. It is exactly the "prioritize urgent orders" pattern from 01-04, with urgency = accumulated minutes.
• Relaxation (new_dist < dist[v]): the atomic operation of every algorithm in this lesson. It means "I have found a faster way to reach v; update".
• Lazy deletion (if u in settled: continue): heapq does not allow updating the priority of an already-inserted element, so when we improve dist[v] we simply insert another entry. The old (worse) versions come out later and are discarded on seeing the node already settled. It is the same stale-entries technique we used in the best-first search of branch and bound (02-03) — not by coincidence: B&B with bound = accumulated cost is a relative of Dijkstra.
• Route reconstruction is the reconstruct(parent, target) of 03-02, unchanged: ALM→HOS returns ['ALM', 'MER', 'CEN', 'HOS'], the true 13 minutes. BFS's thorn, extracted.

A trace of the first steps, to fix the intuition (from ALM):

Look at step 2: the 12-minute direct avenue is beaten before CEN gets settled. That is the entire secret.

Invariant: when a node u leaves the heap with distance d (and gets settled), d is the true minimum distance to u. Why? Any other path to u would have to leave the settled zone through some frontier node w still in the heap. But that w has provisional distance ≥ d (if it were smaller, it would have come out before u), and from w to u you can only add non-negative weights. Bottom line: any alternative measures ≥ d. No surprise is possible.

Complexity with adjacency list + binary heap: each edge triggers at most one heap insertion ⇒ O(m) insertions/extractions costing O(log n) each (the heap holds O(m) entries, and log m = O(log n)): O((n + m) log n). For the street map of a big city (n ≈ 10⁵, m ≈ 3·10⁵), a few million operations: milliseconds. The growth hierarchy of 01-01 in action.

The invariant's argument contains a phrase with fine print: "you can only add non-negative weights". If an edge can subtract, settling nodes becomes premature. A minimal example with logistic meaning: Rutalia rewards certain segments where the van picks up returns on the way back — the segment's net cost (time minus the equivalent saving) can turn out negative.

True optimal path ALM→HOS: ALM→MER→UNI→HOS = 4 + 6 − 2 = 8. But Dijkstra settles HOS as soon as it leaves the heap with 9 (the direct route), before processing UNI (which sits at 10): by the time the reward appears, HOS is already settled and the improvement is discarded. Dijkstra's result: 9. Incorrect, and worst of all it fails silently: no error, no warning. With weights that may be negative, Dijkstra is disqualified.

Bellman-Ford gives up the heap's cleverness and applies systematic force: relax every edge, and repeat the pass |V| − 1 times.

Why do |V| − 1 passes suffice? A simple shortest path uses at most |V| − 1 edges. After pass k, all shortest paths of up to k edges are guaranteed (direct induction). The price of this robustness: O(n · m), far above Dijkstra's cost — on the 10⁵-node street map we are talking ~3·10¹⁰ operations versus Dijkstra's milliseconds. Generality has its price.

A negative-weight cycle is a cycle whose weights sum to < 0. If it is reachable, "shortest path" stops making sense: one more lap always improves things, all the way to −∞. In Rutalia it would appear if the rewards were badly calibrated: add to BONUS the edge HOS→MER with cost −9 and the cycle MER→UNI→HOS→MER sums 6 − 2 − 9 = −5. A van would "gain minutes" by circling forever — an unmistakable sign that the incentive model is broken, not that we have discovered perpetual motion. That is why the detection in pass |V| is no ornament: it is a model validation. (In finance, the same test detects arbitrage opportunities in currency cycles.)

Dijkstra and Bellman-Ford answer "how far is everything from this source?". Rutalia needs something more ambitious: the table of travel times between all zones. We could run Dijkstra from every node (perfectly valid: n runs), but there is an algorithm of remarkable elegance that does it directly on the adjacency matrix of 03-01: Floyd-Warshall.

Its DP subproblem is a gem of a definition (compare with the grid of 01-03, where the subproblem was "best cost up to cell (i,j)"):

D_k[i][j] = minimum cost from i to j using as intermediate nodes only the first k nodes of the list.

• Base case D₀: the adjacency matrix (no intermediates: direct edges only).
• Transition: when node k becomes allowed as an intermediate, either it is not used (D_{k−1}[i][j] stands) or it is used exactly once (D_{k−1}[i][k] + D_{k−1}[k][j]):

Details that matter:

• The loop order is sacred: k (the intermediate) goes outside. With k inside, the algorithm is simply wrong. It is the most frequent mistake when writing it from memory.
• As in the bottom-up DP of 01-03, we overwrite a single matrix instead of storing the n layers D_k: it can be shown that reusing already-updated values from layer k does not break correctness (it can only bring valid improvements forward).
• Complexity: three full loops ⇒ O(n³) and O(n²) memory. For 9 zones, 729 steps: nothing. For 1,000 nodes, 10⁹: the borderline. For an entire street map: unworkable — there you use n runs of Dijkstra over an adjacency list, or the techniques of 06-03.
• It admits negative weights (without negative cycles); a negative cycle betrays itself because some D[i][i] ends up < 0. A free test.

Result of running the code on the canonical network — the matrix of minimum travel times in minutes between all zones:

Observe: D[ALM][CEN] = 9 (not 12: nobody in their right mind takes the congested avenue) and D[ALM][HOS] = 13 (the 3-segment path BFS scorned). The matrix is symmetric because the graph is undirected.

And here a circle closes with module 2: this matrix is what fed the TSP. In 02-02 we used Euclidean distances between the 10 stops for didactic simplicity, but in a real city the van does not fly in a straight line: the "distance" between two stops is the shortest-path time through the streets. The professional workflow is exactly this pipeline: (1) street graph → (2) Floyd-Warshall or n×Dijkstra → travel-time matrix → (3) TSP/B&B/GA/ACO on that matrix. Modules 2 and 3 were never separate topics: they were the two halves of one system.

Selection guide: no weights → BFS; weights ≥ 0 and one source → Dijkstra; possible negative weights or a need to validate the model → Bellman-Ford; all pairs and moderate n → Floyd-Warshall (or n runs of Dijkstra if the graph is sparse and the weights non-negative).

A passing mention: when only one specific destination matters and an estimate of what remains is available (for example, straight-line distance), there is A*: essentially "Dijkstra with a compass", steering the exploration towards the goal instead of expanding in a circle. It belongs to heuristic state-space search and we will develop it in 04-03; for now it is enough to know that its heart is exactly the Dijkstra of this lesson.

• Using Dijkstra with negative weights: it fails silently, as we saw with the reward (it returns 9 instead of 8). Add a non-negative-weights assert when building the graph if you are going to use Dijkstra; it is the most profitable validation in this lesson.
• Forgetting lazy deletion: without the if u in settled: continue, every stale heap entry reprocesses the node and re-relaxes its edges; the result stays correct, but the cost blows up. With it, correct and efficient.
• Putting Floyd-Warshall's k loop innermost: it produces incorrect results that are hard to spot on small graphs (sometimes it coincides by luck). The intermediate k goes outside, ALWAYS. Verify against the ALM row of the table.
• Stopping Bellman-Ford after |V|−1 passes without the extra pass: you swallow the negative cycles and return meaningless distances. Pass n is the one that validates the model.
• Rerunning Dijkstra for every source-destination pair of a full table: either Floyd-Warshall, or one Dijkstra per source, reusing its result for the n−1 destinations. Never n² runs.
• Tip: always keep parent alongside dist. A distance without its route is half an answer; the courier needs the itinerary, not just the number.

1. Everyday route. Using dijkstra and the reconstruct of 03-02, compute the fastest route and its duration from EST to PAR in the canonical network. Check the result against the lesson's matrix.
2. The avenue — who is it for? The ALM–CEN edge (12 min) looks useless: Dijkstra never uses it from ALM. Write code that, using Floyd-Warshall's matrix D, checks whether the edge belongs to the shortest path of any pair of zones (hint: edge {u,v} of weight w lies on some shortest path between i and j if D[i][u] + w + D[v][j] == D[i][j], in one of the two orientations). Should Rutalia ask the city council to remove it from the street map?
3. Treacherous reward. Starting from the BONUS graph, add the edge HOS -> MER with cost −9 and verify that bellman_ford raises the negative-cycle exception. Then find the maximum (least negative) cost that edge can have without creating a negative cycle, reasoning over the cycle MER→UNI→HOS→MER.

Exercise 1:

EST→UNI (3) →HOS (5) →PAR (7) = 15 minutes, matching cell [EST][PAR] = 15 in the matrix. Two different algorithms, one truth: that is how you validate software.

Exercise 2:

The avenue takes part in the shortest path of no pair: a faster alternative always exists (at the very least, going around through MER or RIO). Remove it? Not necessarily: shortest paths describe the nominal regime. If roadworks close MER–CEN and RIO–CEN at the same time, the avenue becomes the only fast way into the Center. Redundancy ≠ uselessness — the robustness analysis of 03-02 and the flow analysis of 03-05 complete the picture that shortest paths alone don't give.

Exercise 3:

The cycle is MER→UNI (6) →HOS (−2) →MER (x), summing 4 + x. It is negative if x < −4. Therefore the minimum admissible cost for the edge is −4 (at −4 the cycle sums 0: legal though degenerate; at −5 it is already negative and the model breaks). Operational moral: Rutalia's rewards must be calibrated by looking at the graph's cycles, not at each segment in isolation.

We have gone from counting segments to adding minutes. Dijkstra — BFS with the heap of 01-04, seed cashed in — solves the standard case with non-negative weights in O((n+m) log n) thanks to a greedy invariant provable in three lines; Bellman-Ford pays O(n·m) in exchange for tolerating negative rewards and detecting negative cycles, which are modeling errors dressed up as bargains; and Floyd-Warshall, dynamic programming over the matrix with the intermediate node as a dimension, delivers in O(n³) Rutalia's complete travel-time matrix — the piece connecting this module to module 2's TSP: first shortest paths over the street map, then route optimization over the resulting matrix. Dijkstra has also taught us something deeper: a greedy algorithm can be provably optimal if the problem has the right structure. In 02-02 we saw greedy algorithms fail; in the next lesson, 03-04, we meet the other star case where greed wins with a certificate: minimum spanning trees, with Kruskal — time to cash in the second seed of 01-04, the union-find — and Prim.