We leave lists behind and return to the stop network we modeled as a graph in 03-04 — this time with the star question of any mobility app: how many minutes does it take, at minimum, from one stop to each of the others? The algorithm that answers it was announced in 03-02 by name: Dijkstra, "the greedy that is optimal". After watching greedy strategies fail (greedy_change, supervisor_route), here we study the one that triumphs: why its greedy choice — always settling the closest pending stop — is irrevocably correct when the weights are not negative, how to implement it efficiently with a priority queue (heapq), and how to reconstruct the path as well as its cost. We will trace it in full from Main Square and close with its complexity and its one kryptonite: negative weights.

1. The RutaBus network as a weighted graph
2. The problem: shortest paths from a single source
3. The greedy idea and why it works
4. Sidebar: what a heap / priority queue is
5. Implementation with heapq
6. Full trace from Main Square
7. Reconstructing the path: predecessors
8. Complexity and the negative-weights limitation

In 03-04 the network was an adjacency dictionary that only said who connects with whom. To talk about times we need to add weights: the travel minutes of each segment. It is enough to replace the neighbor lists with neighbor → minutes dictionaries:

Minimal vocabulary: the stops are the vertices (V = 5), the segments are the edges (E = 6) and the minutes, their weights. Our graph is undirected — each segment appears in both directions with the same weight —; if L3 had a one-way segment, we would simply record it in one direction only, and everything that follows would work the same.

The cost of a path is the sum of the weights of its segments. From Main Square to Central Hospital there are several: via North Station (4 + 5 = 9), via River Park directly (2 + 8 = 10), via River Park and University (2 + 3 + 6 = 11). The single-source shortest paths problem asks, for a given source, the minimum distance to all the other stops — exactly what RutaBus needs in order to answer "how long from here?" for a user standing at Main Square.

Why is nothing we already have good enough? The backtracking from 03-04 (inspection_routes) would enumerate every possible path — exponential. And watch out for the "path with the fewest stops" trap: the direct segment RP→CH (8 min) loses against the detour RP→UNI→CH (9 min... no, 3+6=9, here the direct one wins — but MS→CH via NS with two segments beats the direct route via RP with two segments). Fewer segments does not mean fewer minutes: you have to count weights, not hops. (Counting hops is what a breadth-first search, BFS, would do — one line of mention and we move on, because with weights it is not enough.)

Dijkstra maintains for each stop a tentative distance (the best found so far, ∞ if none) and applies this greedy loop, pure 03-02:

Among the stops not yet settled, take the one with the smallest tentative distance, declare it final, and relax its edges: for each neighbor, check whether going through the newly settled stop improves its tentative distance.

"Relaxation" is the elementary operation: if dist[stop] + minutes(stop, neighbor) < dist[neighbor], we have found a shortcut and we update.

Why does this greedy choice never go wrong? The argument — a cousin of the exchange argument from 03-02 — rests on a single hypothesis: no weight is negative. Let p be the unsettled stop with the smallest tentative distance d. Could there exist a path to p shorter than d, not yet discovered? That path would leave the settled zone at some point and cross some other unsettled stop q before reaching p. But merely reaching q already costs at least its tentative distance, which is ≥ d (p was the minimum!), and from q to p the remaining segments add up to ≥ 0 (here enters the hypothesis). Total: ≥ d. No detour can beat d, so settling p at d is safe — forever. It is a greedy with the property supervisor_route was missing: every local decision comes with a proven global guarantee.

Priority queue and heap, in four lines. A priority queue is a structure that lets you insert elements with a priority and always extract the one with minimum priority. Its standard implementation is the binary heap: an almost-complete tree stored in a list where every node is ≤ its children, so the minimum always lives at the root (position 0). Inserting (heappush) and extracting the minimum (heappop) cost O(log n) — the element "floats up" or "sinks down" along the ~log₂ n levels of the tree, the same halving count as in 04-01. In Python this comes ready-made in the heapq module, which operates on ordinary lists; with (priority, data) tuples it compares the priority first.

What do we want it for? The greedy step requires locating "the pending stop with the smallest tentative distance" many times. Finding it with a linear sweep would cost O(V) each time; the heap serves it up in O(log V).

Three design decisions worth understanding:

• Stale entries. When a stop's tentative distance improves, we do not edit its old entry in the heap (heaps do not support that gracefully): we add another one with the new distance. The new one, being smaller, will come out first; when the old one eventually surfaces, the if stop in settled: continue throws it away. This is the lazy deletion technique: simpler and, in practice, just as efficient.
• dist starts at infinity (float("inf")): "I don't know any path yet". Floating-point infinity compares correctly against any sum of minutes and avoids treating the "undiscovered" as a special case.
• previous records, for each stop, where it was last reached from with an improvement — the breadcrumb that in section 7 will give us back the full path, not just its cost.

Let's run dijkstra(network, "Main Square"). We abbreviate: MS, NS, CH, RP, UNI. Each row is one iteration of the while that settles one stop:

Result: from Main Square it takes at minimum 0 (MS), 4 (NS), 9 (CH), 2 (RP) and 5 (UNI) minutes. The trace exhibits the two characteristic behaviors:

• The settling order (MS, RP, NS, UNI, CH) is by increasing distance — the greedy frontier expands like a wave from the source.
• Step 3 shows a correcting relaxation: CH had been discovered via RP (10 min) but the route via NS improves it to 9. The tentative distance was just that, tentative; only on being settled (step 5) does it become definitive truth. And step 6 shows the stale entry (10, CH) dying quietly.

dist answers "how much"; the user wants "which way". The answer lies in previous, which after the run holds:

It is the same move as the knapsack reconstruction in 03-03: during the algorithm we do not store the paths (there would be too many, too long), we store one breadcrumb per stop — who last reached it with an improvement — and at the end we walk the breadcrumbs backwards:

Note the structural elegance: the previous pointers form a shortest-path tree rooted at the source — a single dictionary encodes the best path to every stop at once.

Time. Let's count with the tools of 02-01, with V the stops and E the segments:

• Each stop is settled exactly once, and on being settled it relaxes its edges; each edge is therefore relaxed O(1) times per endpoint → O(E) relaxations in total.
• Each improving relaxation does a heappush of O(log·heap size). The heap holds at most O(E) entries (because of the stale ones), and log E ≤ log V² = 2·log V — constant out (01-03) —, so each heap operation is O(log V).
• Extractions: O(V + E) heappop calls, also at O(log V).

Total: O((V + E) · log V). For RutaBus's real network — sparse: each stop connects with 2-4 neighbors, E ≈ 2V — this is nearly linear: with 10,000 stops, on the order of 4·10⁵ heap operations. The alternative without a heap (finding the minimum with a linear sweep) would cost O(V²) — 10⁸ — which only pays off in very dense graphs.

Space: O(V + E) — the dist/previous dictionaries and the heap. Linear auxiliary space, no surprises.

The kryptonite: negative weights. The whole proof in section 3 hung on "the remaining segments add up to ≥ 0". If a weight can be negative — imagine a bonus segment where the bus recovers 4 minutes of schedule — the argument collapses, and the algorithm with it:

Dijkstra from A settles B at distance 3 (it is the smallest tentative: 3 < 5) and declares it untouchable. But the path A→C→B costs 5 + (−4) = 1. The greedy settling — "nothing can beat the current minimum" — was a lie: an apparently expensive detour hid a discount. With travel minutes this does not happen (time does not run backwards), but it does as soon as the weights model costs with refunds, differences or balances. Those graphs call for algorithms that do not settle so cheerfully — and one of them, which moreover answers all-stops-against-all in one go, is exactly the next lesson: Floyd-Warshall.

• Using it with negative weights: it does not warn, it does not fail — it returns incorrect distances with complete self-confidence. If your weights can be negative, Dijkstra is ruled out from the start (section 8).
• Forgetting the stale-entry discard (if stop in settled: continue): the algorithm re-processes stops with old distances; in graphs with many cycles it may give correct results by luck but blow up the cost, or corrupt previous. The duplicate entries in the heap are by design; the discard is their other half.
• Putting the heap tuple the wrong way round ((stop, distance)): heapq compares the first field — you would be ordering alphabetically by stop name, and the "greedy" would settle Central Hospital before River Park without looking at minutes. Priority ALWAYS first.
• Confusing "discovered" with "settled": a stop's tentative distance can improve several times (CH: ∞ → 10 → 9) as long as it is not settled. Treating the first tentative distance as final is reinventing the negative-weights bug without needing them.
• Tip: to debug, print the settled stop and its distance on each iteration. They must come out in non-decreasing order; if you see a step backwards, you have negative weights or a bug — that monotonicity is the algorithm's signature.

Add the stop "South Terminal" connected to "University" (7 min) and to "Central Hospital" (1 min). Trace dijkstra(network, "Main Square") with the table from section 6: settling order, final distances, and previous. In which step does South Terminal improve its tentative distance?

RutaBus wants the shortest path between two specific stops (origin → destination), not to all of them. Modify dijkstra so it can stop early: at which exact moment is it safe to return the answer for destination, and why? (The justification is the heart of the lesson.)

An intern proposes fixing negative weights like this: "I add to every segment a constant K large enough that none stays negative, run Dijkstra, and done". Find the flaw with this counterexample: A→B direct (weight 1) versus A→C→B (weights −1 and 1), with K = 2. Which path is really the shortest and which one does the "fixed" Dijkstra choose?

Solution 1

With ST connected to UNI (7) and CH (1):

South Terminal improves in step 5: discovered via University (12), corrected via Central Hospital (10). previous["South Terminal"] = "Central Hospital", and the path is MS → NS → CH → ST (4+5+1 = 10). Notice: the "expensive" neighbor (CH at 9 min) turned out to be a better gateway than the "cheap" one (UNI at 5) — which is why ST cannot be settled until its turn comes.

Solution 2

You can return dist[destination] at the moment destination is settled (it comes off the heap and passes the stale-entry filter):

Justification: settling is exactly the guarantee that this distance can no longer improve (the argument from section 3, valid because the weights are ≥ 0). Stopping earlier — for example, the first time destination receives a tentative distance — would be incorrect: CH received 10 before 9 in our trace. In the best case (a nearby destination) the saving is huge; in the worst (a distant destination), everything gets settled anyway — best/worst case, 02-03.

Solution 3

Real weights: A→B = 1; A→C→B = −1 + 1 = 0 ← the shortest. With K = 2: A→B = 3; A→C→B = 1 + 3 = 4 → the "fixed" Dijkstra chooses A→B. The flaw: the constant K is charged once per segment, so it penalizes paths with more segments more heavily — it distorts the comparison between paths of different lengths. Adding K does not translate the problem, it swaps it for a different one. Negative weights require algorithms designed for them, not makeup; Floyd-Warshall (next lesson) is one.

Dijkstra delivers what 03-02 promised: a greedy with a proof. By maintaining tentative distances and always settling the closest pending stop — with the guarantee, valid only under non-negative weights, that no detour can beat it — it computes the shortest paths from a source in O((V+E) log V) thanks to heapq's priority queue, and the predecessors dictionary reconstructs the itineraries just as we reconstructed the knapsack in 03-03. The trace from Main Square showed us its signature (settling in order of increasing distance, tentative distances corrected along the way) and the final counterexample showed us its boundary: a single negative weight and greediness goes back to being the sin it was in greedy_change. But RutaBus still has one request that Dijkstra only solves by brute repetition: the website wants the complete matrix of times between all stops. Do we run Dijkstra V times, or is there something better? The answer is the algorithm we announced in 03-03 as "dynamic programming on graphs", which moreover digests negative weights without blinking: Floyd-Warshall.