Dijkstra & Smooth Radio
Smooth radio gets you from the song you're on to the song you asked for without a jarring jump. Every crossfade has a cost — a clash of key, a lurch in tempo — and the station should play the chain with the lowest total cost, even if that means a few extra songs on the way. Counting hops won't find it. This lesson's algorithm will: Dijkstra's shortest path, the idea inside every route planner.
Why BFS isn't enough
BFS finds the route with the fewest edges. Once edges carry different weights, fewest isn't cheapest:
BFS would happily return the one-step jump costing 9. The three-step chain costs 3. BFS's guarantee — "first found is best" — came from every edge costing the same.
Always settle the cheapest song next
Dijkstra's fix is one rule: of all the songs you can reach but haven't settled, settle the one with the cheapest known cost next. With no negative weights, nothing discovered later can undercut it — any other route has to leave through a song that already costs at least as much.
"Give me the cheapest one" is a job for a priority queue, and in Python that's
heapq. Push (cost, song) tuples; heappop always returns the smallest.
import heapq
heap = []
heapq.heappush(heap, (5, "glow"))
heapq.heappush(heap, (2, "drift"))
heapq.heappush(heap, (2, "aura"))
print(heapq.heappop(heap))Relaxation
When you settle a song, look at each transition out of it and ask: is going through here cheaper than the best route I know? If so, lower that neighbour's cost. That update is called relaxation. Step through two rounds of it:
Drift first gets 4 (straight from intro), then relaxes to 3 once glow is settled.
Dijkstra, in full
Put the two together: pop the cheapest entry, relax its neighbours, push any improvement. A song can end up in the heap more than once — an old, pricier entry left behind by a later improvement — so skip entries that are stale.
❓ Cross-question — "Why not remove the old entry instead of skipping it?"
heapqcan't find an item in the middle of the heap without an O(n) scan. Pushing a duplicate and ignoring the stale one when it surfaces ("lazy deletion") keeps every operation O(log n). The heap holds at most O(E) entries, and log E is within a constant of log V.
A song's cost is only final when it's popped, not when it's first pushed. Mark it finished any earlier and a cheaper route that arrives later is ignored:
The cheapest chain is intro → glow → drift, costing 3, but this prints 9. Fix it so a later, cheaper route can still win.
Getting the chain, not just the cost
Exactly like BFS, keep a parent dict — but update it every time you relax,
because a song's best predecessor can change:
When the goal is popped, walk parent back to None and reverse — the same
walk-back you wrote for BFS.
Negative weights break it
Dijkstra's promise was "nothing later can be cheaper". A negative edge breaks it: a route through an expensive song can still come out cheaper after a big discount.
import heapq
graph = {"start": [("a", 2), ("b", 5)], "b": [("a", -4)], "a": []}
best = {"start": 0}
heap = [(0, "start")]
while heap:
cost, song = heapq.heappop(heap)
if song == "a":
print(cost)
break
for nxt, step in graph[song]:
if cost + step < best.get(nxt, float("inf")):
best[nxt] = cost + step
heapq.heappush(heap, (cost + step, nxt))For graphs with negative weights, use Bellman-Ford (below). Smooth radio's costs are never negative, so Dijkstra is the right tool.
What it costs
| Algorithm | Time | Works with |
|---|---|---|
| BFS | O(V + E) | every edge costs the same |
| Dijkstra with a binary heap | O((V + E) log V) | non-negative weights |
| Dijkstra with a plain array scan | O(V²) | non-negative weights, dense graphs |
| Bellman-Ford | O(V × E) | negative weights; detects negative cycles |
heappush / heappop |
O(log n) | — |
Coming from Java/JS:
heapqis Java'sPriorityQueue— but as functions acting on a plain list, and always a min-heap. JS has no built-in heap at all. For a max-heap in Python, push negated keys.
Idioms & real-world patterns
Break ties with a counter
When two costs tie, Python compares the next item in the tuple. If that item can't
be compared — a dict, say — heappush raises TypeError. Put a running counter
between the cost and the payload so the payload is never compared:
Stop when the goal is popped
For one start and one goal, return the moment the goal comes off the heap — its cost is final then. Returning when it's merely pushed is the bug from the fix above.
⚡ Advanced — Bellman-Ford
Bellman-Ford skips the heap and simply relaxes every edge, V − 1 times. After round k, every route that uses at most k edges has been accounted for, and a shortest route never needs more than V − 1. If a V-th round still improves something, there's a negative cycle — a loop that gets cheaper every time round.
⚡ Advanced — A*
Dijkstra expands outward in every direction. A* adds an estimate of the cost still to go — straight-line distance on a map, say — to each heap key, so the search leans toward the goal. With an estimate that never overshoots, it still finds the cheapest route, usually after exploring far less.
🎯 Your turn
Write smoothest_mix(transitions, start, goal). transitions is an undirected,
weighted edge list — [song, song, cost] — and a transition works in both
directions. Return the cheapest chain as {"cost": total, "path": songs}, or
{"cost": -1, "path": []} if no chain exists:
smoothest_mix([["intro", "drift", 4], ["intro", "glow", 1], ["glow", "drift", 2]], "intro", "drift")→{"cost": 3, "path": ["intro", "glow", "drift"]}- the same transitions from
"glow"to"glow"→{"cost": 0, "path": ["glow"]}
Hint — build an adjacency dict both ways, run Dijkstra with heapq, record
parent whenever you relax, and rebuild the path when goal is popped.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅