Dijkstra vs A*: when the heuristic earns its keep
Both find shortest paths. So why does every game engine ship A* and every routing engine ship Dijkstra? A practical comparison.
Dijkstra and A* are siblings. They share the same priority-queue skeleton. The only difference is what you put in the queue: Dijkstra orders by g(n) — the cost so far — while A* orders by f(n) = g(n) + h(n), where h is a heuristic estimating the remaining distance.
When A* shines
On a 2D grid where you have a clean Euclidean or Manhattan distance to the goal, A* explores a fraction of the nodes Dijkstra would. That's why every tile-based game from Civilization to StarCraft uses it.
When Dijkstra wins
On a road network, distances aren't Euclidean — highways, bridges, and one-way streets bend the cost surface. Coming up with an admissible heuristic is hard, and Dijkstra's predictable behavior plays nicely with contraction hierarchies and other preprocessing tricks that real-world routers depend on.
# A* is just Dijkstra with one extra term in the priority
f = g + h(node, goal)
heapq.heappush(pq, (f, g, node))