How Google Maps calculates the shortest distance | Hacker News Reader

How Google Maps calculates the shortest distance

mathsection.com

13 pointsjelliclesfarm15 comments

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.

Yeah 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.

The article is a complete puff piece. There is no substance to it whatsoever.

https://www.quora.com/Does-Google-Maps-use-Dijkstras-algorit... : on Quora

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

"How some random dude supposes Google calculates the shortest distance"

I wish Google had more levers and knobs. For me it would be:

No unprotected left turns into major streets.

I value simplicity over expediency

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.

They're not just using the maximum legal speed.

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).

[0] https://en.wikipedia.org/wiki/Contraction_hierarchies

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.

What you describe (and what Google does of course) is closer to the A* algorithm.

Reply on news.ycombinator.com