# The A* Graph Search Algorithm

A frequently-encountered problem in programming is finding the shortest path between two nodes in a weighted graph. For example, consider a graph where nodes represent cities and edges are highways connecting pairs of cities, with each edge weighted by the driving distance between the cities via that route.

This problem, like the similar travelling salesman problem, is prone to a combinatorial explosion as the number of nodes and edges increases. The naïve approach of simply enumerating all possible routes and choosing the shortest rapidly blows up into a problem which even the fastest supercomputer would require far more time than the age of the universe to calculate.

In 1956, Edsger W. Dijkstra, figured out an algorithm to find the shortest path in a weighted graph which he eventually published in 1959 and is now called the Dijkstra shortest-path algorithm. Dijkstra recalls that he worked out the algorithm in his mind in about twenty minutes without using pencil and paper.

Dijkstra’s algorithm always finds the shortest path and runs much faster than exhaustive search, but it examines paths which inspection of the weights can easily exclude as impossible to be the shortest. In 1968, three researchers at the Stanford Research Institute published the A* search algorithm, which finds the shortest path much faster, albeit at the cost of larger memory consumption in many cases.

The video shows how that A* algorithm can be viewed as a generalisation of Dijkstra’s algorithm by adding a potential to each node (for example, the Cartesian distance between the node and the destination) and using that heuristic to guide the search. Like Dijkstra’s algorithm, A* is guaranteed to always find the shortest path.

Here is the A* algorithm searching for the shortest railroad path between Washington D.C. and Los Angeles in the U.S., using the great circle distance from each railway junction to the destination as the heuristic potential.

5 Likes

Great quote! “one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities”. Of course that was said before we all had supercomputers in our pockets with connections to the world’s largest sometimes correct library, and ChatGPT to do all the work before coming up with a politically correct wrong answer.

Using the latitude and longitude of two points to find the great circle distance is easier than I expected. I see the pruning (that I don’t quite understand) isn’t quite perfect with it wandering up through Chicago, but at least it’s avoiding trying around Hudson Bay. Wonder if that’s how the Garmin that magically computes our semi-annual route between the northern and southern limits of the US works, and how Google’s new AI will affect the Google maps routing that gets used for backup and in-flight entertainment. The two can be quite different on longish trips, both with some head scratching “why the heck did it pick that way”. The older Garmins would say “recalculating” in an obviously irritated voice when you departed from the chosen path, the newer ones are a lot less emotionally invested. Maybe the AI’d Google will restore that, along with saying how much time would have been saved if we’d just listened to our computerized overlords.

The animated map is nice, and entertaining to watch. Do you know if there’s a generalized version that lets you pick start and end points, and maybe alter the speed to make it easier to watch working?

3 Likes