Developed in 1968 by P. Hart, N. Nilsson and B. Raphael, the A* algorithm (pronounced A-star) is an extension of Dijkstra's algorithm. It tries to optimize searches by guessing the traversal direction thanks to heuristics. Thanks to this approach, it is known to be faster than Dijkstra's algorithm, especially for large graphs.
Algorithm principles
In Dijkstra's algorithm, all possible paths are explored. This can be very time-consuming, especially on large graphs. The A* algorithm tries to overcome this problem, with the idea that it can guess which paths to follow and which path expansions are less likely to be the shortest ones. This is achieved by modifying the criterion for choosing the next start node at each iteration. Instead of using only the cost of the path from the start to the current node, the A* algorithm adds another component: the estimated cost of going from the current node to the end node...