5 ms·
As someone who doesn't fully understand these algorithms, are these algorithms the same as what's used in GPS/mapping systems, and potentially even internet rou
by dpcx 15y ago
As someone who doesn't fully understand these algorithms, are these algorithms the same as what's used in GPS/mapping systems, and potentially even internet routing systems?
- keeperofdakeys 15y agoThese kinds of algorithms wouldn't be good for mapping systems as they are - they would send you through lots of side streets. You want to travel on main roads where possible, so you need to 'layer' them (highways, main roads, side streets). You would also try to cache data, which with different layers, might work well. As for internet routing, I do think they use Dijkstra and Bellman–Ford quite a bit.
- dbaupp 15y agoThey would work, just not using the obvious heuristic/distance of physical distance. One could use travel time (smaller roads are slower) or some more complicated weighting which could take into account the size of the road, speed limit, and even include parameters that allow the user to adjust how much it biases towards large roads (for example).
- illicium 15y agoDijkstra's algorithm with low edge weights on fast roads, and high weights on side streets might work.