patternMinor
Is Dijkstras algorithm used in modern route-finding systems?
Viewed 0 times
routeusedsystemsalgorithmfindingdijkstrasmodern
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#33911, answer score: 8
Revisions (0)
No revisions yet.