How does route finding software work?

Question

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.

Answer 1

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.

Answer 2

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.