f = g + h
Every node carries three numbers:
- g(n) — the actual cost of the best known path from the start to n. This is exactly Dijkstra’s distance.
- h(n) — the heuristic: an estimate of the remaining cost from n to the goal.
- f(n) = g(n) + h(n) — the estimated total cost of a route through n.
A* is then exactly Dijkstra with the priority queue ordered by f instead of g. Set h(n) = 0 everywhere and you get Dijkstra back precisely — A* is a strict generalisation, not a different algorithm.
Admissible, consistent, and why it stays optimal
A heuristic is admissible if it never overestimates the true remaining cost. That single property is what guarantees A* finds an optimal path.
The reason: if h never overestimates, then f(n) never overestimates the cost of the best route through n. So when the goal is popped with total cost f, no unexplored node can be hiding a cheaper route — any such node would have had a smaller f and been popped first.
Overestimate, and that breaks. An inflated h can make the true best route look worse than a bad one, and A* will return the bad one. The common heuristics on a grid are admissible by construction:
- Manhattan |dx| + |dy| — admissible when movement is 4-directional, because that is the exact distance with no obstacles.
- Euclidean √(dx² + dy²) — admissible always, since a straight line is the shortest possible route, but weak (too low) on 4-directional grids.
- Zero — admissible and useless: this is Dijkstra.
Note that Manhattan is not admissible if diagonal movement is allowed, because the diagonal route is shorter than |dx| + |dy|. That mismatch is the most common way people accidentally break optimality.
Dijkstra, pointed at the goal
Dijkstra's algorithm expands outwards in all directions, treating every unexplored node as equally worth visiting. On a map, searching from London for a route to Manchester, it spends effort exploring towards Cornwall.
A* fixes that with one change to the priority:
f(n) = g(n) + h(n)
g(n) is the known cost from the start — exactly what Dijkstra uses. h(n) is a heuristic estimate of the remaining cost to the goal. Prioritising by their sum focuses the search along promising directions.
import heapq
def a_star(start, goal, neighbours, cost, h):
g = {start: 0}
prev = {start: None}
pq = [(h(start), start)]
while pq:
_, node = heapq.heappop(pq)
if node == goal:
break
for nxt in neighbours(node):
ng = g[node] + cost(node, nxt)
if ng < g.get(nxt, float("inf")):
g[nxt] = ng
prev[nxt] = node
heapq.heappush(pq, (ng + h(nxt), nxt)) # g + h
return reconstruct(prev, goal)
The only difference from Dijkstra is ng + h(nxt) where Dijkstra pushes ng. With h = 0, A* is Dijkstra.
Admissibility: the condition for correctness
A* returns the optimal path if the heuristic is admissible — it never overestimates the true remaining cost.
The reasoning: if h underestimates, then f(n) = g(n) + h(n) is a lower bound on the true cost of any path through n. So when the goal is popped with the smallest f, no unexplored path can be shorter, and the path found is optimal.
If h overestimates, A* may pop the goal while a better path is still queued, and it returns a suboptimal route quickly. Sometimes that is an acceptable trade — deliberately inflating h ("weighted A*") gives faster, slightly worse paths, and games use it routinely.
| Heuristic | Admissible for |
|---|
| 0 | Anything — this is Dijkstra |
| Straight-line (Euclidean) distance | Movement in any direction |
| Manhattan distance | Grid movement, 4 directions only |
| Diagonal (Chebyshev) distance | Grid movement, 8 directions |
| Actual remaining cost | Perfect — explores only the optimal path |
A stronger property, consistency (or monotonicity), means h never decreases by more than the edge cost along any edge. A consistent heuristic guarantees each node is finalised once, so no node needs reopening — which is why standard implementations can use a closed set safely.
Choosing the heuristic is the whole design
The heuristic decides how much better than Dijkstra A* is, and getting it wrong is the usual failure.
Too weak (close to 0) and A* degenerates towards Dijkstra, exploring almost everything.
Not admissible and the result is suboptimal. The classic mistake on a 4-directional grid is using Euclidean distance: it underestimates correctly, so it is admissible — but Manhattan distance is a tighter underestimate and therefore explores far less. Conversely, using Manhattan distance when diagonal movement is allowed overestimates and breaks optimality.
Too expensive to compute and the per-node saving is lost. h is evaluated for every node examined.
The practical rule: use the tightest admissible estimate that is cheap to compute, and match it to the actual movement rules.
For road networks the straight-line distance is admissible but weak, because roads are not straight. Production routing engines use landmark-based heuristics: precompute distances from a few hundred landmark nodes, and use the triangle inequality to derive much tighter bounds. That is one of the techniques that makes continental route planning interactive.
What the heuristic buys, and the condition it must satisfy
A* is Dijkstra's algorithm plus a guess about how far the goal still is. The guess decides everything: a good one cuts the search enormously, a merely plausible one makes it return the wrong path. Both are visible on a grid you can print.
Guided experiments
- See the search become directional. Press Run Algorithm and watch the explored region. It stretches toward the goal rather than spreading in a circle — that elongation is h doing its job.
- Turn the heuristic off. Set Heuristic to the zero or Dijkstra option and press Reset Grid, then run again. The explored area balloons into a symmetric blob. The path found is the same length; the work to find it is far greater.
- Compare Manhattan against Euclidean. Run each in turn on the same grid. Manhattan is the larger estimate on a 4-directional grid, so it prunes harder and expands fewer nodes while still finding an optimal route.
- Slow it down and watch the frontier choose. Set Execution Speed to 1 and run. Each expansion picks the lowest f, so the frontier repeatedly reaches toward the goal and only falls back sideways when it meets an obstacle.
What usually goes wrong
- An inadmissible heuristic. Scaling h up (multiplying by 1.5, say) makes the search much faster and quietly non-optimal. That trade is sometimes worth making — weighted A* is a real technique — but it must be a decision, not an accident.
- Manhattan distance with diagonal movement. Overestimates, so paths stop being optimal. Use the octile heuristic when diagonals are allowed.
- Forgetting that a node’s g can improve. With a merely admissible (not consistent) heuristic, a node may be reached again more cheaply after being expanded. Either use a consistent heuristic or re-open such nodes.
- An expensive heuristic. h is evaluated constantly. If computing it costs more than the expansions it saves, A* is slower than Dijkstra despite exploring fewer nodes.
What to remember
A* orders its priority queue by f = g + h, where g is the cost so far and h estimates the cost remaining, which focuses the search along the direction of the goal instead of expanding uniformly. Provided h never overestimates, the path returned is still optimal — and the better the estimate, the fewer nodes get expanded. With h = 0 it degenerates exactly to Dijkstra, which is the cleanest way to see what the heuristic is buying.
Where it is used
- Game pathfinding. The default algorithm for moving units around a map, usually on a grid or navigation mesh.
- Robotics. Motion planning over occupancy grids, often with variants handling continuous space.
- Route planning. Real navigation systems use A* with landmark heuristics, or contraction hierarchies which precompute shortcuts.
- Puzzle solving. Sliding tiles, Rubik's cube and similar, where the heuristic is a relaxation of the puzzle — for the 15-puzzle, the sum of Manhattan distances of each tile from its home.
- Word ladders and state-space search generally, where the graph is generated on demand.
- Automated planning in AI, where the state space is enormous and heuristics are essential.
The puzzle case illustrates a general technique for inventing heuristics: solve a relaxed version of the problem. Ignoring that tiles block each other gives the Manhattan-distance heuristic, which is admissible because the real puzzle can only be harder.
The variants
| Variant | Change | Use |
|---|
| Weighted A* | f = g + w×h with w > 1 | Faster, suboptimal by at most a factor of w |
| IDA* | Iterative deepening with an f-limit | Memory-constrained; puzzles |
| Bidirectional A* | Search from both ends | Long paths |
| Jump point search | Skip symmetric grid paths | Uniform-cost grids — large speed-up |
| D* / D* Lite | Repair the path when the map changes | Robotics with unknown obstacles |
| Anytime A* | Return a path quickly, improve it | Real-time constraints |
Memory is A*'s real weakness. It stores every node it has seen, and on a large state space that exhausts memory long before time becomes the constraint. IDA* addresses this by using depth-first search with an increasing f-limit and O(depth) memory, at the cost of re-expanding nodes.
Jump point search is worth knowing for grid games: on a uniform-cost grid, many paths are symmetric — going right-then-up is the same cost as up-then-right — and JPS skips all but one representative. It can be an order of magnitude faster than plain A* on open maps.
Comparing the search algorithms
| Algorithm | Priority | Optimal | Explores |
|---|
| BFS | Insertion order | Yes, unweighted | Everything within distance d |
| Dijkstra | g(n) | Yes | Uniformly outwards |
| Greedy best-first | h(n) | No | Straight at the goal |
| A* | g(n) + h(n) | Yes, if h is admissible | Towards the goal |
Greedy best-first search is the instructive contrast: prioritising by h alone is fast and can produce badly suboptimal paths, because it ignores the cost already incurred. A* is exactly the correction — balance what the path has cost against what remains.
Questions people ask
Is A* always better than Dijkstra? When a useful heuristic exists, yes — it explores far fewer nodes for the same answer. Without one, it is Dijkstra.
What if my heuristic overestimates? The path found may be suboptimal. That is sometimes an acceptable trade for speed.
Which heuristic for a grid? Manhattan for 4-directional movement, diagonal/Chebyshev for 8-directional, Euclidean for free movement.
Why does it use so much memory? It keeps every discovered node. IDA* trades time for memory when that binds.
Can it handle negative weights? No — like Dijkstra, its correctness assumes non-negative edges.
How do I get the path, not just the cost? Record each node's predecessor when its g value improves, then walk back from the goal.
Recap in one screen
- A* prioritises by
g + h: cost so far plus an estimate of what remains. - With
h = 0 it is Dijkstra; with a good heuristic it explores dramatically fewer nodes. - The heuristic must never overestimate (admissible) or the path may be suboptimal.
- Use the tightest cheap estimate matching the movement rules — Manhattan for 4-way grids, not Euclidean.
- Memory is the practical limit; IDA*, jump point search and weighted A* are the standard responses.