A* (pronounced “A star”) is a graph-search algorithm for finding a minimum-cost path from a start node to a goal. It was introduced by Peter Hart, Nils Nilsson, and Bertram Raphael in their 1968 paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” published in the IEEE Transactions on Systems Science and Cybernetics. Their contribution was a formal way to fold problem-specific knowledge, expressed as a heuristic, into the mathematics of graph searching.
A* expands nodes in order of an evaluation function that adds two parts: the cost already spent to reach a node from the start, and a heuristic estimate of the cost remaining from that node to the goal. By preferring nodes whose total estimated cost is lowest, the search is steered toward the goal rather than spreading out blindly in every direction, while still tracking the real cost paid so far.
The paper’s central result concerns admissibility. When the heuristic never overestimates the true remaining cost, A* is guaranteed to return a least-cost path, and the authors prove an optimality property: under that condition no other search of the same kind that is guaranteed to find a shortest path expands fewer nodes. If the heuristic estimate is zero everywhere, A* reduces to a uniform-cost search closely related to Dijkstra’s algorithm.
A* became one of the most widely used pathfinding methods in practice. It is a staple of video-game movement, robot navigation, and route planning, wherever a good estimate of remaining distance, such as straight-line distance to the target, can be used to make the search both correct and fast.