9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – babou Dec 6 '14 at 8:10
  • 1
    $\begingroup$ 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$. $\endgroup$ – jmite Dec 6 '14 at 10:44
5
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Raphael Dec 6 '14 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.