05b — Shortest paths and A*

A* is named explicitly in the prep email, and it is the one algorithm here most candidates have only heard of. It is also the easiest to explain well, because it is Dijkstra plus one idea.

Prereqs: 05 · Reading: 6 min · Cards: 10 · Code: code/graphs.py

The map

Every shortest-path question reduces to one decision: what do the edge weights look like? If they are all equal, BFS already answers it and anything heavier is over-engineering. If they are positive, Dijkstra. If some are negative, Bellman-Ford. If you know the destination and can estimate the remaining distance, A* gets the same answer while expanding far fewer nodes.

Everything else — lazy deletion, admissible heuristics, negative cycle detection — is detail hanging off that one decision. Make the decision out loud, with the reason, and the rest follows.

What decides your score here

Not reaching for Dijkstra when BFS suffices. If every edge costs the same, using a heap where a queue would do reads as pattern-matching rather than thinking.

Explaining why negative weights break Dijkstra. The interesting part is not that it fails, it is how: it does not crash or hang, it returns a wrong answer silently. Saying that shows you understand the invariant rather than the API.

Naming both A* properties. Admissible and consistent are different things, one implies the other, and most candidates conflate them.

Dijkstra, and the invariant that carries it

Dijkstra is greedy: it always expands the unfinalised node with the smallest known distance. The invariant that makes it correct is that when a node comes off the heap, its distance is final — nothing found later can improve it, because everything remaining is already at least as far.

That is exactly what a negative edge destroys. A negative edge further along could improve a node you already finalised, so the premise fails. The algorithm does not detect this; it just returns something wrong. A silent wrong answer is worse than a crash, and saying so is the right instinct to show.

The implementation detail worth explaining is lazy deletion. Python's heapq has no decrease-key, so instead of updating an entry you push a new one with the better distance and skip stale entries on pop:

d, u = heapq.heappop(heap)
if d > dist.get(u, inf):
    continue                    # stale — a better entry was pushed after this one

The heap can therefore hold up to E entries, which is where the O(E log V) bound comes from. A Fibonacci heap would give O(E + V log V) in theory but is slower in practice because of the constants — worth mentioning, not worth implementing.

A*, which is Dijkstra with a guess

Dijkstra orders its heap by g(n), the cost so far. A* orders it by f(n) = g(n) + h(n), where h estimates the remaining cost to the goal. That is the entire difference.

With h identically zero, A* is Dijkstra. A better h expands fewer nodes and returns the same answer. That framing — "A* with a zero heuristic degenerates to Dijkstra" — is the cleanest way to introduce it.

Two properties, and they are not the same thing.

Admissible means h never overestimates the true remaining cost. This is what guarantees the path found is optimal. Overestimate and you may commit to a worse path and never revisit it.

Consistent (or monotonic) means h(n) ≤ cost(n, m) + h(m) for every neighbour — the triangle inequality applied to the heuristic. This guarantees each node is closed exactly once, with no need to reopen. Consistency implies admissibility; the converse is false, and with a merely admissible heuristic you must be prepared to reopen closed nodes.

On a grid the heuristics are: Manhattan for four-directional movement, Chebyshev for eight-directional, and Euclidean for free movement. The asymmetry is the detail that separates knowing about A* from being able to use it: Euclidean on a four-direction grid is still admissible — it underestimates, so it is merely weaker and expands more nodes. But Manhattan on an eight-direction grid overestimates, because a diagonal move covers two Manhattan units at once. It is inadmissible, and you lose the optimality guarantee entirely.

Bellman-Ford, and the constraint that reveals it

Bellman-Ford relaxes every edge V−1 times, which is enough because no simple path has more than V−1 edges. It accepts negative weights, at O(V·E). And if one more pass still improves a distance, there is a negative cycle reachable from the source — because only a cycle you can loop around could keep reducing.

The reason to have it ready is Cheapest Flights Within K Stops. A limit of K stops maps exactly onto K+1 rounds of relaxation, which is Bellman-Ford's structure rather than Dijkstra's. Dijkstra would find the globally cheapest path while ignoring the hop limit — the right answer to the wrong question. Recognising that mapping is the solution.

One implementation detail: relax from a snapshot of the previous round's distances. Relaxing in place lets a single round chain through several edges and allows more hops than the limit permits.

Say it

Cover the answers. Out loud, in English.

Now do this

Three problems. The third is the one that teaches A*.

1. Network Delay Time — 20 min. Plain Dijkstra with lazy deletion, from memory.
2. Cheapest Flights Within K Stops — 30 min. Say out loud why this is Bellman-Ford and not Dijkstra.
3. Shortest Path in Binary Matrix — 30 min. Solve it with BFS first, then redo it with A* and count the nodes each expands. That comparison is the best A* exercise there is.

Stop when you can state the A*-to-Dijkstra relationship and both heuristic properties without hesitating.