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.
