# A* Shortest Path Algorithm

An A* Shortest Path Algorithm is a shortest path algorithm that uses a uniform-cost heuristic that assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish.

**Context:**- It can (typically) be a Dynamic Programming-based Algorithm.
- It can be implemented by an A* Shortest Path-based System.

**Counter-Example(s)****See:**Graph Search Algorithm, Pathfinding, Graph Traversal Algorithm.

## References

### 2017

- (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/A*_search_algorithm Retrieved:2017-12-5.
- In computer science,
**A***(pronounced as "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently directed path between multiple points, called nodes. It enjoys widespread use due to its performance and accuracy. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although other work has found A* to be superior to other approaches.^{[1]}Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first described the algorithm in 1968.^{[2]}It is an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance by using heuristics to guide its search.

- In computer science,

### 2016

- http://en.wikipedia.org/wiki/Pathfinding#A*_algorithm
- QUOTE: A* is a variant of Dijkstra's algorithm commonly used in games. A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found. If there is a path of length x between the start and finish, and the minimum distance between a node and the finish is greater than x, that node need not be examined.
^{[1]}A* uses this heuristic to improve on the behavior relative to Dijkstra's algorithm. When the heuristic evaluates to zero, A* is equivalent to Dijkstra's algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When the value of the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance.) As the value of the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many applications (such as video games) this is acceptable and even desirable, in order to keep the algorithm running quickly.

- QUOTE: A* is a variant of Dijkstra's algorithm commonly used in games. A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found. If there is a path of length x between the start and finish, and the minimum distance between a node and the finish is greater than x, that node need not be examined.

### 2012b

- http://en.wikipedia.org/wiki/A*_search_algorithm
- QUOTE: In computer science,
**A***(pronounced "A star" (13px listen)) 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. … It is an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance (with respect to time) by using heuristics.

- QUOTE: In computer science,

### 2009

- (Korf, 2009) ⇒ Richard E. Korf. (2009). “Artificial Intelligence Search Algorithms.” In: Algorithms and Theory of Computation Handbook. ISBN:1584888180
- QUOTE: The A* algorithm [14] combines features of uniform-cost search and pure heuristic search to efficiently compute optimal solutions. A* is a best-first search in which the cost associated with a node is f(n) = g(n) + h(n), where g(n) is the cost of the path from the initial state to node n, and h(n) is the heuristic estimate of the cost of a path from node n to a goal. At each point a node with lowest f value is chosen for expansion. Ties among nodes of equal f value are broken in favor of nodes with lower h values. The algorithm terminates when a goal node is chosen for expansion. A* finds an optimal path to a goal if the heuristic function h(n) is admissible, meaning it never overestimates actual cost. … The main drawback of A*, and indeed of any best-first search, is its memory requirement. Since the open and closed lists are stored in memory, A* is severely space-limited in practice, and will exhaust the available memory on current machines in minutes.

### 1968

- (Hart et al., 1968) ⇒ Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths". In: IEEE Transactions on Systems Science and Cybernetics SSC4, 4(2). doi:10.1109/TSSC.1968.300136.