A* search algorithm

A* (pronounced "A-star") is a graph traversal and pathfinding algorithm that is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path (with respect to the given weights) from source to goal. One major practical drawback is its O ( b d ) {\displaystyle O(b^{d})} space complexity where d is the depth of the shallowest solution (the length of the shortest path from the source node to any given goal node) and b is the branching factor (the maximum number of successors for any given state). In practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as by memory-bounded approaches; however, A* is still the best solution in many cases. Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search. The A* algorithm terminates once it finds the shortest path to a specified goal, rather than generating the entire shortest-path tree from a specified source to all possible goals.