Eli5: How does navigation software plot out the best route?

56 views
0

I’ve tried googling it and all I get is “Map starting point + map second point + MAGIC = best route”.

In: 1

A road map can be represented as a connected graph. Imagine a bunch of dots (nodes) representing intersections, and lines connecting them representing roads. Each line has some information associated with it i.e. the length of that road segment, the speed limit, etc.

Your map software stores these graphs. There are [algorithms](https://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms) that will find quick routes between any two points on a connected graph. So it’s just a matter of finding the nodes closest to your starting location and ending location, and finding the quickest path between them.

At it’s most fundamental, what it’s doing is just trying every single possibility and measuring which one is the fastest. There are tons of ways to optimize this so it only checks a much smaller more reasonable subset of all possibilities, but these are going to vary from software to software. At it’s core it’s still “try a bunch of routes and see which one is the fastest”.