2

Although I've never really dug into it, I've always assumed mapping out directions in a GPS unit is done with A* or Fibonacci-heaps at a higher level and Dijkstra's algorithm for smaller graphs. Are there any other algorithms being used that aren't immediately obvious?

1

Stack Overflow has a detailed response to a similar question, I won't try to reproduce it here. For GPS receivers without internet access, likely all major routes are precomputed, and then only supplemented for the end-nodes when heading off freeways. The Google blog has some background on their 'draggable directions', but alas no algorithmic meat.

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.