Google Maps' Secret Route-Finding Algorithm Revealed

The algorithm used by Google Maps to find the fastest route is based on decades-old math and clever shortcuts.

Dijkstra's algorithm, developed in 1956 by Edsger Dijkstra, assigns a cost to each location based on the shortest route discovered so far. This approach ensures that the algorithm finds the shortest route without having to test every possible combination, making it remarkably efficient for its time.

However, as road networks have grown and navigation requests increased, Dijkstra's algorithm became too slow. A* was developed as an improvement, adding a shortcut that estimates how close each location is to the destination, prioritizing locations heading toward the target.

The latest technique used by Google Maps is called a customizable contraction hierarchy, which ranks intersections according to their importance in the wider network and creates mathematical 'shortcuts' between important points. This approach was tested and calculated a route across North America in just 200 microseconds, making it around 35,000 times faster than Dijkstra's algorithm.