A* search algorithm

A* (pronounced "A-star") is a <a href="/facts/Graph_traversal/vFjrnHxr">graph traversal</a> and <a href="/facts/Pathfinding/x9Ho1cvp">pathfinding</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that is used in many fields of <a href="/facts/Computer_science/lN3pEyPz">computer science</a> due to its completeness, optimality, and optimal efficiency. Given a <a href="/facts/Weighted_graph/W0MqKkyE">weighted graph</a>, a source <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">node</a> and a goal node, the algorithm finds the <a href="/facts/Shortest_path_problem/g4nsrswr">shortest path</a> (with respect to the given weights) from source to goal.
One major practical drawback is its 
 
 
 
 O
 (
 
 b
 
 d
 
 
 )
 
 
 {\displaystyle O(b^{d})}
 
 <a href="/facts/Space_complexity/nsnAW5cV">space complexity</a> 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 <a href="/facts/Branching_factor/VpEhS2G2">branching factor</a> (the maximum number of successors for any given state), as it stores all generated nodes in memory. Thus, in practical <a href="/facts/Travel-routing_system/gs0hPAzl">travel-routing systems</a>, 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.
<a href="/facts/Peter_E._Hart/pKSPzx0Q">Peter Hart</a>, <a href="/facts/Nils_Nilsson_(researcher)/5dGvCFC7">Nils Nilsson</a> and <a href="/facts/Bertram_Raphael/jBKCpD5T">Bertram Raphael</a> of Stanford Research Institute (now <a href="/facts/SRI_International/flSHunVK">SRI International</a>) first published the algorithm in 1968. It can be seen as an extension of <a href="/facts/Dijkstra%2527s_algorithm/ehun88jl">Dijkstra's algorithm</a>. A* achieves better performance by using <a href="/facts/Heuristic_(computer_science)/PM2qkoa2">heuristics</a> to guide its search.
Compared to Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified source to a specified goal, and not the shortest-path tree from a specified source to all possible goals. This is a necessary <a href="/facts/Trade-off/xY3nXnJN">trade-off</a> for using a specific-goal-directed <a href="/facts/Heuristic/BcBEkv9c">heuristic</a>. For Dijkstra's algorithm, since the entire shortest-path tree is generated, every node is a goal, and there can be no specific-goal-directed heuristic.

A* search algorithm open-in-new

A* search algorithm