A* Search Algorithm
Also known as: A* algorithm, A-star algorithm, A* search
The A* Search Algorithm, developed by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael in 1968, is an optimal path-finding algorithm that combines the benefits of Dijkstra's algorithm with heuristic guidance. It efficiently finds the shortest path by balancing actual distance from the start with estimated distance to the goal.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Apply A* when you need to find optimal paths in graphs where a good heuristic function is available. It is particularly effective for pathfinding in games, robotics, and route planning where informed search can substantially reduce computation. Use it when speed matters but optimality is required. For cases without a reliable heuristic, use Dijkstra's algorithm instead.
Strengths & limitations
- Optimal pathfinding when the heuristic is admissible
- Much faster than Dijkstra or breadth-first search when good heuristics are available
- Flexible: works with any admissible heuristic function
- Well-suited for single-goal pathfinding problems
- Extensive real-world validation in games, robotics, and navigation systems
- Optimality depends on the admissibility of the heuristic function
- Performance degrades significantly with poor or inadmissible heuristics
- Memory usage can be substantial in large search spaces (maintains open and closed sets)
- Requires explicit domain knowledge to design good heuristic functions
Frequently asked
What is an admissible heuristic and why does it matter?
An admissible heuristic never overestimates the true cost to the goal. This property guarantees that A* finds the optimal path. If a heuristic overestimates, A* may miss shorter paths and return suboptimal solutions.
How do you design a good heuristic for a problem?
Good heuristics are based on domain knowledge and problem structure. For grid-based pathfinding, Manhattan or Euclidean distance works well. For more complex problems, consider relaxing constraints or using pattern databases to compute admissible heuristics.
What is the difference between A* and Dijkstra's algorithm?
Both find optimal paths, but A* uses a heuristic to prioritize exploration toward the goal, making it much faster when a good heuristic is available. Dijkstra explores uniformly in all directions and is safer when heuristics are unreliable.
Can A* guarantee finding the shortest path?
Yes, A* guarantees the shortest path when the heuristic is admissible (never overestimates true cost). With inadmissible heuristics, optimality is not guaranteed.
Sources
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. DOI: 10.1109/TSSC.1968.300136 ↗
- Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson. ISBN: 978-0-13-604259-4
How to cite this page
ScholarGate. (2026, June 3). A* Search Algorithm. ScholarGate. https://scholargate.app/en/operations-research/a-star-search-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Bellman-Ford AlgorithmOperations Research↔ compare
- Dijkstra AlgorithmOperations Research↔ compare