Dijkstra's algorithm explores the graph equally in all directions. If I look for the route from Bologna to Florence, Dijkstra pays the same attention to roads towards Venice and towards Milan, until its «wave» of distances reaches Florence. It is correct, but it wastes work: I know Florence is to the south, and I would like the algorithm to know it too.
A (pronounced «A star») does exactly that. It adds to Dijkstra an estimate* of how far the goal still is and uses this estimate to prioritise the vertices that seem to be heading in the right direction. Introduced in 1968 by Hart, Nilsson and Raphael, it is still the standard algorithm for pathfinding in video games, robotics and route planning.
The formula f = g + h
For each vertex n, A* considers:
- g(n): the cost of the best path found so far from the start to n (the same value as in Dijkstra);
- h(n): the heuristic estimate of the cost from n to the goal;
- f(n) = g(n) + h(n): the estimated total cost of a route through n.
The priority queue is ordered by f instead of g. If h is always 0, A* is exactly Dijkstra. The more informative h is, the more directly the search heads for the goal.
import heapq
def a_star(adj, start, goal, h):
g = {start: 0}
parent = {start: None}
heap = [(h(start), start)]
while heap:
f, u = heapq.heappop(heap)
if u == goal:
break
if f > g[u] + h(u):
continue
for v, w in adj[u]:
ng = g[u] + w
if v not in g or ng < g[v]:
g[v] = ng
parent[v] = u
heapq.heappush(heap, (ng + h(v), v))
return g.get(goal), parent
Admissibility: the condition for optimality
A heuristic is admissible if it never overestimates the true remaining cost: h(n) ≤ true cost from n to the goal. With an admissible heuristic, A* always returns an optimal path.
The idea of the proof: as long as the queue holds a vertex along the optimal path, its f value is at most the optimal cost, because h does not exaggerate. So a suboptimal path, which has a larger f, cannot be extracted first.
A stronger condition is consistency (or monotonicity): for every edge (u, v) with weight w, h(u) ≤ w + h(v). In words: the estimate never drops by more than the cost of the edge travelled. With a consistent heuristic every vertex, once extracted, already has its final cost, as in Dijkstra. Almost all geometric heuristics used in practice are consistent.
Classic heuristics on grids
In games and robotics the graph is often a grid of cells. The choice of heuristic depends on the movements allowed:
| Allowed movement | Heuristic | Formula (dx, dy = coordinate differences) |
|---|---|---|
| 4 directions only | Manhattan | dx + dy |
| 8 directions, diagonal cost 1 | Chebyshev | max(dx, dy) |
| 8 directions, diagonal cost √2 | Octile | max(dx, dy) + (√2 − 1) · min(dx, dy) |
| Free movement | Euclidean | √(dx² + dy²) |
Using a heuristic designed for a different kind of movement is a common mistake. Manhattan distance on a grid with diagonals overestimates the cost, loses admissibility and can produce non-optimal paths.
On road networks, a common choice is the straight-line distance divided by the network's maximum speed: an estimate of time that can never exceed the real time.
The trade-off between speed and quality
Sometimes a near-optimal path found quickly is worth more than a perfect one found late. Weighted A* uses f = g + ε · h with ε > 1. The search becomes «greedier», explores fewer vertices, and the cost of the path found is guaranteed to be no more than ε times the optimum. With ε = 1.2, for example, you accept at most 20% extra in exchange for a much faster search.
At the opposite extreme, a heuristic that is too weak (close to zero) keeps optimality but brings A* back towards Dijkstra's behaviour.
Common practical problems
- Memory: A keeps every discovered vertex. On huge spaces, such as puzzle games with billions of states, variants like IDA are used, which repeat depth-first searches with increasing thresholds on f.
- Ties in f: in open areas many vertices share the same f and A* explores all of them. Breaking ties in favour of the higher g (the more advanced vertices) greatly reduces the work.
- Unreachable goal: if no path exists, A* explores the whole component before giving up. It pays to check connectivity first, perhaps with precomputed components.
Beyond maps
A* works on any problem that can be expressed as a search in a state space: solving the 15 puzzle (with the sum of the tiles' Manhattan distances from their final positions as the heuristic), planning sequences of actions, aligning sequences. You only need to define the states, the moves with their cost and an admissible estimate of the remaining distance.
In short
- A* orders the search by f = g + h, where h estimates the remaining cost to the goal.
- With an admissible heuristic, one that never overestimates, the path found is optimal.
- The heuristic must match the allowed movements: Manhattan, Chebyshev, octile, Euclidean.
- Weighted A* trades a guaranteed loss of quality for a faster search.
- The same scheme applies to any search in a state space.
