4 ms·
”It's because everything has to be precomputed for fast lookups” I don’t see how that can be true. With, conservatively, 50 million destinations, that would me
by Someone 7y ago
”It's because everything has to be precomputed for fast lookups”
I don’t see how that can be true. With, conservatively, 50 million destinations, that would mean 25E14 different precomputed routes (edit, that’s exactly what the paper you reference argues: An extreme way to accelerate queries is to precompute all shortest path distances d(s, t). However, this is impractical for large graphs since it requires quadratic space and preprocessing time.)
Also, the average GPS without any internet connectivity can compute routes. Surely, those don’t store those precomputed routes.
What likely is true is that it may be a bit harder to do a bicycle route planner. Slightly simplifying, a planner for cars, given two places A and B relatively far apart, ‘just’ needs to find the best route from A to any on-ramp to a highway, from any highway to B, and a route only on highways between the on- and off-ramps.
On the other hand, bike routes that have to be planned typically will be a bit shorter.
Together, that means it isn’t that hard to compute routes on the fly. https://routeplanner.fietsersbond.nl/ https://routeplanner.fietsersbond.nl/ does exactly that, giving you options such as “shortest route”, “fewest interruptions”, “racing”, “fewer cars”, or “recreational”.
- Doctor_Fegg 7y agoIt's kind of true. Routing algorithms like Contraction Hierarchies and Transit Node Routing don't precompute every possible A-B pair, but they do store so many "shortcuts" (i.e. the best route between common As and Bs) that a route lookup will quickly converge on one of these precomputed routes for all but its first and last sections. It's similar to the way that we intuitively navigate by car - if you drive from (say) London to Glasgow, you don't bother weighing up the many options: rather, you take whatever local roads get you to the M1 fastest, then follow M1, M6, M74, and then whatever local roads get you to your exact destination.