4

I'm asking at a pretty high, language independent, level.

How does route finding (as found in Google Maps 'Get directions' or a GPS) work? I can't believe it tries every conceivable route and chooses the shortest/fastest etc. There must be some logical way of finding the best route given a start and end point.

Any sort of explanation would be great.

1

2 Answers 2

7

You should read up on the shortest path problem and Dijkstra's algorithm. Both these are used to determine the path to take between two points. Google Maps (and other mapping applications) add additional features (such as rerouting, etc), but these two concepts are the basic premise of how the problem is solved.

1

A very old post, but I just looking for this particular question and I found a good article with the explanation: http://blog.kdgregory.com/2011/12/how-gps-calculates-routes.html

Basically, it uses an A* search algorithm and route classification (short-route, long-route, etc.) to reduce computational and memory requirements.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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