In computer science, A* (pronounced "A star")
is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes.
Noted for its performance and accuracy, it enjoys widespread use.
Peter Hart, Nils Nilsson and Bertram Raphael first described the algorithm in 1968.
It is an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance (with respect to time) by using heuristics.
However, when the heuristics are monotone, it is actually equivalent to running Dijkstra.