Give the edges price tags and BFS's floor-by-floor guarantee collapses — fewest hops is no longer cheapest. Swap the queue for a heap and the guarantee comes back: settle whatever is cheapest right now, and it stays cheapest forever.
Chapter 15 handed you a beautiful free lunch: on an unweighted graph, BFS floors are shortest paths. This chapter is what happens when the lunch stops being free — when edges carry weights, and "shortest" means cheapest, not fewest. One idea carries the whole chapter: keep expanding the cheapest thing on the frontier, and use a heap (Chapter 14's almost-sorted pile) to know what that is.
The cast: Network Delay Time Medium is Dijkstra played straight. Cheapest Flights Within K Stops Medium adds a budget that breaks Dijkstra's greed. Path with Minimum Effort Medium swaps the objective from sum to worst step. And Swim in Rising Water Hard is where Chapter 9's binary-search-on-the-answer trick comes back, exactly as promised.
BFS's shortest-path guarantee rests on one silent assumption: every edge costs the same. The queue processes nodes in floor order, floor number = edge count, and edge count = cost. The moment weights appear, edge count and cost divorce. A two-hop route priced 2 + 1 beats a one-hop route priced 9 — but BFS reaches the one-hop node first, stamps it "done," and never looks back. Wrong answer, delivered confidently.
So what actually broke? Not the frontier idea — expanding outward from the source is still right. What broke is the order. BFS's queue expands nodes in order of hops from the source; what we need is order of cost from the source. The fix is almost embarrassingly small: replace the FIFO queue with a priority queue keyed on cost-so-far. That single swap is Dijkstra's algorithm. Everything else — visited set, neighbor loop, the shape of the code — survives from Chapter 15 nearly untouched.
It helps to picture both as water. BFS is water spreading on a flat floor: the wavefront reaches everything at distance d before anything at d+1. Dijkstra is water flooding uneven terrain: it always spills into the lowest-cost dry spot next, wherever that is. Different geometry, same physics.
Run Dijkstra as an auction. At every round, the frontier — nodes you've priced but not finalized — sits in a heap, each entry a ticket reading "I can reach node X for cost c." The auctioneer pops the cheapest ticket and settles that node: its cost is now final, pinned, never revisited. Then the freshly settled node offers new tickets to its neighbors: "my cost plus this edge." Repeat until the heap runs dry.
Why is the auctioneer allowed to be so decisive? Here's the whole proof, one breath: suppose node u holds the cheapest ticket, price d. Any other route to u must exit the settled region through some frontier ticket — which costs ≥ d, because u's was the cheapest — and then travel additional edges. If edges can't be negative, "additional" can only mean "more expensive." So no future discovery beats d. Settle it and move on.
Watch the auction below. Settled costs pin in green; frontier tickets queue up in the heap strip, cheapest first. Note the moment node C's direct ticket (cost 6) loses to a detour through E (cost 5) — and note the stale cost-6 ticket left rotting in the heap. We'll deal with that corpse in the next section.
The textbook version of Dijkstra wants a decrease-key operation: when a cheaper route to a frontier node appears, reach into the heap and lower that node's existing entry. Python's heapq can't do that, Scala's PriorityQueue can't do that, and — good news — nobody needs it. Interview Dijkstra uses lazy deletion instead:
That skip line is load-bearing. Without it you re-settle nodes at worse costs, or at best redo work; with it, each node settles exactly once and every extra ticket costs one pop and one comparison. The heap holds at most one entry per push, and each edge pushes at most once, so the whole thing runs in O(E log E) — every edge relaxation pays one heap operation. Since E ≤ V², log E ≤ 2 log V, and everyone writes it as O(E log V) with a clean conscience.
Reread the one-breath proof from Section 2. Its final step was: any alternative route travels additional edges, and additional edges only add cost. A negative edge breaks exactly that sentence. Now an expensive-looking detour can end with a −10 edge and undercut a ticket you already settled — but "settled" meant "never revisit," so Dijkstra ships the wrong answer without a flicker of doubt. The algorithm isn't slightly off with negative weights; its correctness argument evaporates.
The honest tool for negative edges is Bellman-Ford: forget the clever ordering, just relax every edge in the graph, and do that whole sweep V−1 times. Round 1 gets every best path of ≤ 1 edge right, round 2 every path of ≤ 2 edges, and so on — a shortest simple path has at most V−1 edges, so V−1 rounds suffice. It costs O(V·E) — brute, unbothered, correct. (If a V-th round still improves something, you've found a negative cycle: "cheapest path" doesn't even exist.)
Here's the interview reality: negative-edge problems are rare, but Bellman-Ford's rounds-are-edge-counts idea is not. It's about to solve the k-stops problem for us — and if "fill a table where round r depends only on round r−1" sounds suspiciously like dynamic programming, trust the suspicion. Bellman-Ford is DP wearing a graph costume; Chapter 20 makes that formal.
Cheapest Flights Within K Stops Medium: cheapest route from source to destination using at most k intermediate stops. Surely Dijkstra? No — and the reason is instructive. Dijkstra's whole power is permanently settling each city at its cheapest-ever cost. But under a stop budget, a city's cheapest route might burn too many stops to be useful, while a pricier-but-shorter route is the one that lets you still reach the destination in budget. Dijkstra settles the cheap one and throws the useful one away. Greed needs a single notion of "best" per node; the budget gives every node two axes of best.
Bellman-Ford's rounds fix it, because rounds count edges. Run exactly k+1 relaxation rounds (k stops = k+1 flights), and crucially, read each round's improvements only from the previous round's snapshot — that's what stops a bargain from chaining through more flights than the budget allows within a single round. After round r, each node holds its cheapest cost using ≤ r flights. Done. Equivalently, you can run BFS floor-by-floor (Chapter 15 style) carrying costs instead of a visited set — same table, different clothes.
Drag the budget below and watch the cheapest route to T physically change shape: with one stop it's forced through the expensive top route; more budget lets it wander the cheap southern scenic route.
Path with Minimum Effort Medium: hike a grid of elevations from corner to corner, where a route's effort is the single largest elevation jump along it — minimize that. Nothing is being summed. Is this still a shortest-path problem?
Yes — because Dijkstra never actually required addition. Look at what the proof used: extending a path must never make it cheaper. Addition of non-negative weights has that property, but so does max: the worst step of a longer path can only stay the same or get worse. So keep the entire auction and change one line — the relaxation. Instead of cand = d + w, write cand = max(d, w): "the effort of this extended route is the worst thing on it." Cheapest-frontier settling remains exactly as valid, and you get minimize-the-maximum in O(E log V).
This move — keep the machine, swap the objective — is worth stating in the interview out loud: "Dijkstra works for any path cost that can't decrease as the path grows; I'm replacing + with max." It upgrades you from someone who memorized an algorithm to someone who owns it.
Swim in Rising Water Hard: an n×n grid of distinct elevations; at time t every cell with elevation ≤ t is underwater, and you can swim between flooded neighbors. What's the earliest t at which you can swim from the top-left corner to the bottom-right? Squint: it's minimize-the-maximum again — the answer is the smallest possible value of the highest cell your path must cross. So Dijkstra-with-max solves it directly, relaxing with max(d, elevation).
But Chapter 9 promised its answer-space trick would return, and this is the appointment. Ask the yes/no question: "at water level t, does a path exist?" — answerable with one plain BFS over flooded cells (Chapter 15 tech, no weights in sight). And feasibility is monotonic in t: more water can only open cells, never close them, so the answers read no, no, …, no, yes, yes, …. A monotonic boundary is binary-search bait. Search the level axis, run a BFS per probe, and the flood's first passable moment falls out in O(n² log M).
Play both roles below: drive the water level by hand and watch connectivity flip, then let the binary search hop the level axis and corner the boundary in six probes. (A third correct tool exists, for the connoisseur: sort cells by elevation and union-find them in as the water rises — Chapter 16's dynamic-connectivity machine, moonlighting.)
The whole chapter compresses into a four-line dispatch table. Read the problem, find the row:
And one row you'll almost never need but should be able to name: genuinely negative edges → full Bellman-Ford, O(V·E) — brute, unbothered, correct.
The pattern, as a whiteboard skeleton:
Network Delay Time Medium: a signal leaves node k; directed edges carry travel times; when does the last node hear it — or return −1 if some node never does? That's "single-source shortest paths to everyone, then take the max," i.e. Dijkstra played completely straight. Read the code as Chapter 15's BFS with three edits: the queue became a heap, the visited set became a settled-cost map, and the neighbor loop learned to add weights. Everything else is muscle memory.
The Scala version makes one idiom explicit: its PriorityQueue is a max-heap, so we flip the ordering to get min-heap behavior — and instead of a settled set, it skips any popped entry whose cost no longer matches the best known, which is the same stale-ticket test in different clothes.