4 ms·
How Google Maps calculates the shortest distance
- leeoniya 8y agoor 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
- zahreeley 8y agoIt shows you the options
- osrec 8y agoThe 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"
- superwayne 8y agoGoogle 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.
- osrec 8y agoYeah that wouldn't surprise me. I can imagine they've got some smart heuristics built in too to come up with suboptimal routes that are good enough.
- throw0u1t 8y agoThe article is a complete puff piece. There is no substance to it whatsoever.
- jelliclesfarm 8y agohttps://www.quora.com/Does-Google-Maps-use-Dijkstras-algorithm-If-so-can-you-explain-how-they-discretize-the-world https://www.quora.com/Does-Google-Maps-use-Dijkstras-algorit... : on Quora
- Waterluvian 8y agoI wish Google had more levers and knobs. For me it would be: No unprotected left turns into major streets. I value simplicity over expediency
- eigenvector 8y agoOften, 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!).
- panarky 8y ago> 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. They're not just using the maximum legal speed.
- asdfasgasdgasdg 8y ago"How some random dude supposes Google calculates the shortest distance"
- ams6110 8y agoI 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.
- xiphias2 8y agoWhat you describe (and what Google does of course) is closer to the A* algorithm.
- superbaconman 8y agoI 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'.
- mady902 8y agoWell, 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.
- abhishekjha 8y agoDé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). [0] https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies