Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 0 down vote accepted

Stackoverflow 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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