A* & Heuristic Search
In short: A* is Dijkstra with one change: instead of ordering the heap by
g (cost so far), it orders by f = g + h, where h is a heuristic guess of
the cost still to go. As long as h never overestimates the true remaining
cost (it is admissible), A* still finds the cheapest route, but expands far
fewer junctions, because junctions pointing away from the goal get a large h
and wait. An overestimating h breaks the guarantee and can return a worse
route.
A driver at the depot, in the north-west corner of town, taps a pickup at the harbour in the south-east, and Meridian's live map has to answer at once. Dijkstra would get it right, but it settles junctions in rings around the start, spending as much effort away from the harbour as towards it. It has no idea where the harbour is.
You do. The harbour is south-east, and on a street grid you can't get there in fewer minutes than the number of blocks between you. A* is Dijkstra with that one piece of knowledge added, and it still guarantees the cheapest route.
One change to Dijkstra
Dijkstra pops the junction with the smallest g, the cost so far. A* pops the junction with the smallest
where h is a heuristic: a guess of the cost still to go from n to the goal. Junctions in the goal's direction get small h and come off the heap first; junctions behind the start get large h and wait, often forever.
The guess has one job, and one rule. It must never overestimate the true
remaining cost. A heuristic like that is called admissible. On Meridian's grid,
every road takes at least as many minutes as the blocks it spans, so the block
distance |x − gx| + |y − gy| is admissible: no real drive can beat it.
Here's A* on the town map, from the depot to the harbour. Each badge shows g + h once a junction has been reached, and the starting badges are just h:
A* orders its frontier by g + h. With a guess that never overshoots, it heads for the goal, expands five of nine junctions, and still finds the cheapest route.
Every junction starts with h, its block distance to the harbour. No road is faster than its blocks, so h never overshoots. 9 nodes, 12 edges, undirected.
The picture's claim is easy to check. Count how many junctions each search pops before it reaches the harbour:
import heapq
pos = {"depot": (0, 0), "mill": (2, 0), "quay": (4, 0), "west": (0, 2), "plaza": (2, 2),
"east": (4, 2), "park": (0, 4), "market": (2, 4), "harbour": (4, 4)}
roads = [("depot", "mill", 2), ("mill", "quay", 3), ("depot", "west", 2), ("mill", "plaza", 2),
("quay", "east", 2), ("west", "plaza", 4), ("plaza", "east", 2), ("west", "park", 3),
("plaza", "market", 3), ("east", "harbour", 2), ("park", "market", 2), ("market", "harbour", 2)]
graph = {n: [] for n in pos}
for a, b, m in roads:
graph[a].append((b, m))
graph[b].append((a, m))
def expanded(weight):
h = lambda n: weight * (abs(pos[n][0] - 4) + abs(pos[n][1] - 4))
best, heap, done = {"depot": 0}, [(h("depot"), "depot")], []
while heap:
f, n = heapq.heappop(heap)
if n in done:
continue
done.append(n)
if n == "harbour":
return len(done)
for m, w in graph[n]:
if best[n] + w < best.get(m, 99):
best[m] = best[n] + w
heapq.heappush(heap, (best[m] + h(m), m))
print(expanded(1), expanded(0))Building A*
The code is Dijkstra's with f in the heap, and g kept in the tuple:
Step through the first expansion by hand. The frontier sorts by g + h, not by g:
Both neighbours tie at f = 8, so the tuple's second item, the name, breaks the tie. Any tie-break is correct; it only changes which of two equally promising junctions goes first.
When the guess overshoots
A bigger h makes the search more eager: it expands fewer junctions. So why not multiply it by 3? Here's a small map where the direct way to the harbour crosses a slow bridge:
import heapq
pos = {"depot": (0, 0), "bridge": (2, 0), "harbour": (4, 0), "north": (0, 2), "ne": (4, 2)}
roads = {"depot": [("bridge", 9), ("north", 2)], "bridge": [("harbour", 2)],
"north": [("ne", 4)], "ne": [("harbour", 2)], "harbour": []}
def h(n):
return 3 * (abs(pos[n][0] - 4) + abs(pos[n][1] - 0)) # the guess, tripled
best = {"depot": 0}
heap = [(h("depot"), "depot")]
while heap:
f, node = heapq.heappop(heap)
if node == "harbour":
print(best[node])
break
for nxt, minutes in roads[node]:
if best[node] + minutes < best.get(nxt, float("inf")):
best[nxt] = best[node] + minutes
heapq.heappush(heap, (best[nxt] + h(nxt), nxt))An overestimate inflates f along the good route, so a worse route reaches the goal with a smaller f and gets popped first. Admissibility is exactly the condition that stops this: along the cheapest route, f never exceeds the true cheapest cost, so every junction on it comes off the heap before any dearer arrival at the goal.
Dropping g altogether is the same mistake in a purer form. Ordering by the guess alone is greedy best-first search: fast, and wrong whenever the direct way is slow.
This prints 11, the bridge route. The cheapest route, round by north, costs 8. Make it A* instead of greedy best-first search.
A stronger property, consistency, says h drops by no more than each road's cost:
h(u) ≤ minutes(u, v) + h(v). Block distance has it. With a consistent h, a
junction's g is final the first time it is popped, exactly like Dijkstra, so the
stale-entry check is all the bookkeeping you need.
Your A*, drawn
This runs A* on a block of road works (# is closed) and writes each expanded
cell's cost into it. Run it as it is, then set W = 0 and watch Dijkstra flood the
whole grid for the same answer. Then try W = 3: fewer cells, and a longer route.
Your A*. Each number is the cost at which a cell was expanded. A good guess keeps the expanded region narrow; a weight of 0 floods it.
You should see 20 cells expanded for a route of 11 at W = 1, 44 at W = 0, and
17 at W = 3, but with a route of 15. That trade, fewer expansions for a bounded
loss of quality, is sometimes worth taking on purpose (it's called weighted A*),
but never by accident.
How much does aiming save?
On an open grid, Dijkstra's settled region for a trip of d blocks is a diamond of about 2d² cells. A good heuristic keeps A* to a corridor about 4 cells wide along the route, roughly 4d cells. The ratio is d/2: 5 times the work for a 10-block trip, 50 times for a 100-block cross-town trip, 150 times at 300 blocks. It keeps growing with distance, which is why aiming matters most for exactly the long trips drivers ask for.
When blocks are a weak guess, because some roads are slow, you can precompute a
stronger one. Pick a few landmarks, store their distances to every junction, and
use the triangle inequality: |d(L, goal) − d(L, n)| never exceeds d(n, goal).
The capstone exercise builds that.
A*'s worst case is still Dijkstra's: every push and pop is a heap operation, so
it's O((V + E) log V) time, and the heap plus the g/parent maps are
O(V) space — a bad heuristic never costs more than plain Dijkstra, it just
stops saving you anything.
Interview-style: the road-works permit
A van must cross a grid of blocks, some closed for road works. It carries permits that let it drive through at most k closed blocks. What is the fewest number of blocks it must drive?
The trap is treating a cell as the whole state. Reaching a cell with two permits
left is not the same as reaching it with none. The honest state is
(row, col, permits used), a grid stacked k + 1 layers deep, and A* with block
distance runs on those states unchanged. The boss exercise builds it.
What it costs
| Order the heap by | Guarantee | |
|---|---|---|
| Dijkstra | g | cheapest route |
| A*, h never overestimates | g + h | cheapest route, usually far fewer expansions |
| Weighted A* (w × h, w > 1) | g + w·h | route at most w times the cheapest |
| Greedy best-first | h | none |
❓ Cross-question — "Isn't straight-line distance always admissible?" For distance, yes. On Meridian's grid, block distance is better: larger, so fewer expansions, and still never over. For time, divide by the top speed first.
Quick practice
import heapq
pos = {"a": (0, 0), "b": (2, 0), "c": (0, 3), "goal": (2, 3)}
graph = {"a": [("b", 2), ("c", 3)], "b": [("goal", 4)], "c": [("goal", 2)], "goal": []}
h = lambda n: abs(pos[n][0] - 2) + abs(pos[n][1] - 3)
g, heap = {"a": 0}, [(h("a"), 0, "a")]
while heap:
f, cost, node = heapq.heappop(heap)
if cost > g.get(node, float("inf")):
continue
if node == "goal":
break
for nxt, w in graph[node]:
if cost + w < g.get(nxt, float("inf")):
g[nxt] = cost + w
heapq.heappush(heap, (cost + w + h(nxt), cost + w, nxt))
print(g["goal"])KeyErrorWalking parent back from the goal crashes with KeyError. Add the missing parent update.
🎯 Your turn
Write astar_route(junctions, roads, start, goal). junctions lists
[name, x, y] on the street grid; roads are two-way [a, b, minutes], never
faster than their block distance. Use block distance to the goal as h, and return
{"cost": minutes, "path": junctions}, or {"cost": -1, "path": []} with no route:
astar_route([["depot", 0, 0], ["mill", 2, 0], ["plaza", 2, 2], ["harbour", 4, 4]], [["depot", "mill", 2], ["mill", "plaza", 2], ["plaza", "harbour", 4]], "depot", "harbour")→{"cost": 8, "path": ["depot", "mill", "plaza", "harbour"]}
Hint: Dijkstra with (g + h, g, junction) in the heap, a stale-entry check,
and a parent walk when the 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 Meridian's router is built. ✅