Ch.11: Algorithms: Dijkstra vs A* Pathfinding

0:00 Picture this: your map app sends you off the highway into a neighborhood maze. It looks wrong, then you sail past a mile of stopped traffic. Yeah. More turns, more streets. How is that the shortest path? Because shortest means cheapest total. The slow bridge route costs 19 minutes; the five-road detour costs 11. 11 wins. So today we dig into Dijkstra and A-star, two algorithms built for that kind of answer. Same engine underneath, one twist apart. And the real puzzle is how either of them can promise the route it found will never be beaten. That promise is the whole show, and now we earn it.

0:39 So before any of this runs, somebody flattens the world into three things. Places become nodes, connections become edges, and every edge carries a number, a cost. Minutes, dollars, network latency, risk, whatever you care about. And the algorithm never sees a road or a router or a game tile. It sees the graph you handed it, nothing else. Which means the weight is an opinion, sort of. For example, price the edges by airfare instead of miles, and Tokyo can sit closer to you than London, so your travel app books Tokyo first because the total is cheaper.

1:13 Huh. I had never filed the weights as editorial before. The math feels so objective from the outside. The loop is objective. The map it runs on is a design decision, and that split matters for everything coming next. Now, the setup is almost embarrassingly simple. Every node starts at infinity, which is just the math way of saying no idea yet. The start gets zero. And then the numbers shrink as routes get discovered? Exactly. Let's say some route reaches a node for 12. That node now holds a ticket reading best known so far, 12. Not final, just the current best offer.

1:51 I like the ticket, because you can already feel it getting torn up. So there's a whole rim of the search where nodes hold these tentative tickets. That rim has a name, the frontier. Behind it, costs are settled for good. On it, everything is still up for negotiation. Then comes the inner loop itself, and the textbook name for it is relaxation, which honestly sounds like a spa day. Very zen, yes. Nothing says inner peace like knocking on every neighbor's door to renegotiate their commute. The least relaxing relaxation in computer science.

2:25 Here's the actual move. Imagine you're standing on a node whose cost is six, and an edge worth three leads to that neighbor holding the 12. Six plus three is nine. Nine beats 12. Yeah. So you tear up the ticket, write nine, and scribble one more thing on it: came through the six. That little note is how the final route gets rebuilt at the end. And that's genuinely everything the algorithm does. No listing of routes, no cleverness. Just thousands of tiny local questions: can I get you a better deal than the one written down?

3:00 Repeated corrections, all the way down. Which means the only mystery left is the order you process them in. But hold on. Every ticket is tentative, and the map is full of roads nobody has looked at yet. Some cheaper deal could always be hiding three towns over. So when Dijkstra grabs the cheapest node on the frontier and stamps it final, why should I believe that? Prove it to me. Okay, let's try to break it. Our popped node costs five, and its frontier neighbors sit at seven and 10. Now invent a secret cheaper route to it, anything under five.

3:35 Fine. I mean, some hidden back road that gets there for four. That back road still has to enter explored territory somewhere, and every entrance is on the frontier. So its bill starts at seven or 10 before the sneaky part even begins, and with no negative edges it only ever grows. Oh, man. I see the wall. Seven plus anything that isn't negative will never come in under five. The secret route was doomed before it started. Which is why popping the minimum is safe. Picture spilling water onto a bumpy concrete floor: it fills the lowest dips first, and a full dip never drains back down.

4:13 That is the invariant. The water level only goes up. So the moment a node leaves the queue at its minimum, the door locks behind it. That gives you the promise we opened with, proved. Now, none of that proof mentioned speed. Correctness came from the invariant. The queue's only job is finding the cheapest ticket without rummaging every time. Yep, the priority queue. Basically a waiting room where whoever holds the lowest number is always seated next to the exit. Yeah, that waiting-room picture is right.

4:45 If the map keeps each node's outgoing edges in a list, an adjacency list, a binary heap keeps the queue from rummaging through every ticket. The work grows with the nodes plus the edges, with logarithmic queue work on each operation. And heaps got their own episode, so no internals today. Fair. And the heap earns that bound because it gets hammered constantly: one useful pop per settled node, plus a queue write for every successful deal. One wrinkle I always trip on, though. We keep tearing up tickets, but the queue still holds the old numbers.

5:20 So what happens when a stale 12 finally pops out? You glance at your notes, see that node settled at nine ages ago, and toss the 12 in the trash. For example, I got burned by skipping that check once. My toy router processed the same node twice, and I patched it with a duplicate counter I did not understand for a week. The result is a queue you can trust even while it's holding garbage. With the queue mechanics in place, let's run the whole loop once on a tiny map: home to office, past a cafe, a gym, a library.

5:56 Home pops at zero and makes its offers: the cafe gets a four, the gym a seven. The cafe is the cheapest thing anywhere, so it locks next. Its offers ripple out: four plus two hangs a six on the library, and four plus four would hang an eight on the gym, which shrugs it off and keeps its seven. One correction accepted, one rejected, side by side. Then the library locks, then the gym, and when the office pops, its cost is provably cheapest. The came-through notes walk the route backwards. Tidy. And notice what we never did.

6:34 We never listed whole routes and compared them. The path assembled itself out of local corrections. That's the entire machine, no hidden parts. But that whole proof leaned on one quiet assumption: no edge makes a trip cheaper. Break it, and the failure is a quiet nightmare. Say a node locked at five; later a route reaches 10, and its next edge costs minus eight. Hold on. 10 minus eight is two. That beats the five we already called done. The wall crumbles, because a longer route just got cheaper at the last hop.

7:08 And I didn't realize for the longest time why those would even exist. Who builds a road with a negative price? They're real. Take the concrete case of an electric car on a steep downhill: regenerative braking pours charge back into the battery, so that leg profits you. Currency arbitrage graphs pull the same trick with money. Right. And on those maps, this whole approach is simply the wrong tool. There's a slower algorithm, Bellman-Ford, built for exactly that, and that's all we'll say about it today.

7:39 One footnote so nobody panics: a zero-cost edge is fine. Five plus zero is still five. The invariant only dies below zero, which means everyday cost maps stay safely inside the guarantee. So with negative edges quarantined, back to friendly maps, and one complaint left. A routing engineer will eventually ask: why does my service burn its whole latency budget exploring states in every direction before it touches the goal? Guilty as charged, because Dijkstra has no idea where the goal is. It's completely goal-agnostic.

8:11 It grows that puddle evenly on every side and only notices the destination when it accidentally bumps into it. Which is perfect when you genuinely want distances to everywhere at once, like a router does. And kind of heartbreaking when you want one specific place. So now you want the impossible: keep the guarantee, but aim the flood. Turns out that wish has a name, and wait till you hear how little it changes. And that wish became A-star. Hart, Nilsson, and Raphael formalized it in 1968 without changing Dijkstra's engine.

8:45 People assume it's a completely different algorithm. It isn't. The same engine gets one extra number: every candidate is ranked by f equals g plus h, and g is the receipt, the exact cost already paid to stand where you're standing. And h is different in kind. It's a guess, a fast estimate of the cost still remaining to the goal. So a candidate that's cheap so far but pointed the wrong way gets a big h, a big total, and the queue quietly demotes it to the back. Effort flows toward candidates actually closing the distance.

9:18 In water terms, A-star tilts our bumpy floor toward the destination. Gravity still runs the show, dips still fill lowest-first, but the flood rushes down the slope instead of pooling out behind it. Same relaxation loop, same little notes, same reconstruction at the end. The queue changes; the engine doesn't. But h is a guess, right? Doesn't inviting a guess into the math wreck the exact guarantee we spent half this conversation proving? So here's the escape hatch: the guess is only dangerous in one direction.

9:50 The rule is called admissibility. Estimate as optimistically as you like, but never claim the remaining trip costs more than it truly does. And straight-line distance is the classic one only when the cost really tracks physical distance. No route under those rules can beat the crow. But if the weights mean time, tolls, or risk, geometry alone might not be a floor at all. Under-promising preserves the cheapest-path guarantee as long as the search can reopen a node when a better receipt arrives. If your implementation permanently closes popped nodes, you normally want the stronger rule called consistency: across one edge, the estimate cannot drop by more than that edge costs.

10:32 So if I refuse to reopen nodes, consistency is the price of that shortcut? Exactly. Consistency is what makes permanent closure safe. A game developer will push back right there: take a grid where units can't cut diagonals, and that crow-flies number lies short to me constantly. Yes, and that objection is the lesson. The estimate must respect your movement rules, so on that grid you swap in Manhattan distance, counting blocks the way a taxi drives. Always a floor, never a promise. And the dial runs both ways, right? Set h to zero everywhere, the floor untilts, and you're just... Dijkstra again.

11:13 Mathematically identical. Scale h aggressively and the search becomes more goal-directed, often faster, but no longer guaranteed cheapest. Greedy best-first is the far end that ignores g entirely. Some games make choices along that spectrum, eyes open. Now we can see the whole dial, blind flood to reckless sprint. So let's park all this somewhere real, and the cleanest public example is inside the internet itself. Consider OSPF, one of the big routing protocols. Its standard, RFC 2328, literally spells out that every router runs Dijkstra over its map of the network. With operator-assigned link costs as the weights.

11:51 Not miles, not live ping times, just a number somebody chose, you know, to mean prefer this fiber. Then a backhoe somewhere cuts that fiber. Routers flood updated link state, recompute against the changed graph, and use a surviving route when one exists. The algorithm supplies the new tree; flooding, protocol timers, topology, and the implementation help determine how quickly traffic converges. It really is the water finding a new dip. Links for that standard and both original papers are in the description, including Dijkstra's 1959 paper, all of three pages.

12:25 Three pages, and we're still building routing around the idea. And what doesn't the search solve? It only knows the frozen graph you gave it. Moving obstacles, smoothing a jagged route, coordinating a whole group, those are separate systems layered on top. So let's finish by choosing the tool. So let's land the decision rule. One source to many destinations, or no honest way to estimate what remains? What's the move? Dijkstra. Let the flood spread. One known goal, plus a cheap estimate that never overshoots?

12:57 A-star. Tilt the floor. Every edge costs exactly the same? Plain breadth-first search. Just count steps. Negative edges? Neither of today's tools. Use Bellman-Ford. Man, I love that the whole zoo collapses into one question: what do you actually know about your graph? That's the takeaway: a loop handing out better deals, plus a proof that the cheapest settled thing stays settled. Next time, dynamic programming, never solving the same subproblem twice, and the reason your diff tool feels smart. Thanks for listening to Learning Podcasts.