A* is the search algorithm introduced by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968 for finding efficient paths with a heuristic.
The researchers published the method in the paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” A* ranks a candidate node using f(n) = g(n) + h(n): g(n) is the cost already traveled, while h(n) estimates the remaining cost to the goal. This combines the strengths of uniform-cost search and heuristic guidance.
When the heuristic is admissible, meaning it never overestimates the remaining cost, A* can guarantee an optimal path. With a consistent heuristic, it also avoids needing to repeatedly reopen many previously considered nodes.
A* is widely used in robot navigation, video-game pathfinding, route planning, and puzzle solving. Dijkstra’s algorithm can be viewed as a special case in which the heuristic is always zero, but Dijkstra’s algorithm is not generally called A*.