Overview
A* Search is the workhorse of grid pathfinding. It combines Dijkstra's guaranteed shortest paths with a heuristic that estimates the remaining distance to the goal, so it explores far fewer cells by heading roughly in the right direction.
For each node it ranks candidates by f = g + h, where g is the real cost from the start and h is the estimated cost to the goal, focusing the search on the most promising cells.
How A* Search works
- Start with the source node; its g is 0 and its f equals the heuristic h to the goal.
- From a priority queue, expand the open node with the lowest f = g + h.
- For each neighbour, compute a tentative g; if it improves the neighbour's cost, update g, f, and its parent.
- Repeat until the goal is expanded, then reconstruct the path through the parent links.
When to use it
- Real-time pathfinding in games and robotics on weighted grids.
- GPS and map routing, where a distance heuristic dramatically prunes the search.
- Any single-goal shortest-path problem where a cheap, admissible distance estimate is available.
Complexity analysis
A*'s cost depends heavily on the heuristic. In the worst case it is O((V + E) log V) like Dijkstra, but a good admissible heuristic (e.g. Manhattan distance on a grid) prunes most of the frontier. If the heuristic never overestimates the true distance, A* is guaranteed to return a shortest path.
Frequently asked questions
What makes a heuristic 'admissible', and why does it matter?
An admissible heuristic never overestimates the true remaining cost. That guarantee is what keeps A* optimal; if the heuristic overestimates, A* runs faster but may return a path that is not the shortest.
How is A* better than Dijkstra?
Dijkstra expands blindly in all directions; A* uses the heuristic to bias expansion toward the goal, so it usually visits far fewer nodes while returning the same shortest path.