or as i like to call it, how Google Maps finds the most obscure/sceneic route with most turns and narrow streets to save 0.5 miles when a more obvious 2-turn route can be had for the extra 0.5mi.
not having a "prefer simple routes" option is often very aggravating
The article appears to be a gross oversimplification. As is stands, it's a lot of words to convey the fact that "Google uses Dijkstra's algorithm to calculate the shortest distance"
Google Maps most probably does not even use Dijkstra. According to my Algorithmics lecture notes, Dijkstra has O(|V|^2) which is too slow for large street networks.
Often, the simpler route actually is faster because Google fails to compute a realistic time penalty for all of its additional turns, or account for the fact that you can't blast down a residential street at 60kph even if that's the legal limit there.
Over-optimization of routes on Google Maps is borderline comical some times, when Google wants you to make 2 extra turns to get somewhere on the same street that you're already on because the parallel road on the next block has a speed limit that's 5% higher so it thinks it's faster.
Bad routes from Google (or Uber's built-in navigation) are a big part of why Uber/Lyft use has become so frustrating for me, especially when Google gives illegal or dangerous directions (make a U-turn right now even though there's a median in the way!).
> you can't blast down a residential street at 60kph even if that's the legal limit
Google knows how fast cars actually drive on that residential street, on different days of the week, at different times of day, and considering realtime traffic.
I would have imagined it went something like how a person reads a map: first look at the straight line between starting point and destination, then look for arterial roads closest to that.
I wish navigation would take weather and road conditions into account. The last thing I want is taking a bunch of back roads at 3am in the middle of the winter just because it's 'shorter'.
Well, that is an interesting thought given both the data are locally available. Isn't road conditions already available like the given road is blocked because of work in progress.
Déjà vu? I spent a good 30 minutes yesterday on blogposts about how google/uber calculates the shortest distance and found conflicting answers oscillating between Dijkstra's algorithm and [0]Contraction hierarchies(which I didn't understand much).
16 comments
[ 2.6 ms ] story [ 55.2 ms ] threadnot having a "prefer simple routes" option is often very aggravating
No unprotected left turns into major streets.
I value simplicity over expediency
Over-optimization of routes on Google Maps is borderline comical some times, when Google wants you to make 2 extra turns to get somewhere on the same street that you're already on because the parallel road on the next block has a speed limit that's 5% higher so it thinks it's faster.
Bad routes from Google (or Uber's built-in navigation) are a big part of why Uber/Lyft use has become so frustrating for me, especially when Google gives illegal or dangerous directions (make a U-turn right now even though there's a median in the way!).
Google knows how fast cars actually drive on that residential street, on different days of the week, at different times of day, and considering realtime traffic.
They're not just using the maximum legal speed.
[0] https://en.wikipedia.org/wiki/Contraction_hierarchies