# Is Dijkstras algorithm used in modern route-finding systems?

Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?

• I guess you mean the routing component that finds your way, once the GPS, which is primarily a Global Positionning Syatem has determined where you are. Yet another case of a tail wagging a dog. – babou Dec 6 '14 at 8:10
• I can't give a source for this, but my current Algorithms lecturer works in industry, and says that $A^*$ is used a lot in practice, especially for GPS. If you use Euclidean Distance as a heuristic, you tend to get improvements over Dijstra's by ignoring paths that are nonsensical in real life. You might already know, but Dijkstra's can be described as $A^*$ with heuristic $h(x) = 0$. – jmite Dec 6 '14 at 10:44

## 2 Answers

Yes, Dijkstra's algorithm is used in modern maps systems. A lengthy and informative discussion can be found in the following question from StackOverflow: What algorithms compute directions from point A to point B on a map?

Google Maps in 2009 used Contraction Hierarchies - see this tech talk.

Since then, some mind-blowing methods have been discovered, capable of doing cross-country routing in fractional milliseconds - the so-called "two-hop labeling distance oracles". See here, or search for "Hub labeling" or "Shortest paths for the masses". I think I heard Bing uses this one. It also has applications like the ability to find the nearest point of interest (e.g. nearest gas station) with a complexity independent on the number of gas stations.

• This seem to be useful references. However, can you a) give citable references and/or b) paint the broad picture of how these work? In particular, do they solve the problem exactly? – Raphael Dec 6 '14 at 9:12