How does the route finder work?

Question

I ask at a fairly high, language-independent level.

How does route search (found in Google Maps "Route Routes" or GPS) work? I can’t believe that he tries all conceivable routes and chooses the shortest / fastest, etc. There must be some logical way to find the best route, taking into account the starting and ending points.

Any explanation would be wonderful.

Answer 1

You should read the shortest path and Dijkstra's algorithm . Both of them are used to determine the path to be taken between two points. Google maps (and other matching apps) add extra features (like redirection, etc.), but these two concepts are the main prerequisite for solving the problem.

Answer 2

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

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