How Google Maps calculates the shortest distance

https://mathsection.com/how-google-maps-calculates-the-shortest-route/?cookie-state-change=1546194774335

by jelliclesfarm • 8 years ago

13 15 8 years ago

leeoniya• 8 years ago

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

osrec2• 8 years ago

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"

superwayne• 8 years ago

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.

osrec2• 8 years ago

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.

throw0u1t• 8 years ago

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

jelliclesfarm• 8 years ago

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

Waterluvian• 8 years ago

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

eigenvector• 8 years ago

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

panarky• 8 years 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• 8 years ago

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

ams6110• 8 years ago

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.

xiphias2• 8 years ago

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

superbaconman• 8 years ago

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

mady902• 8 years ago

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.

abhishekjha• 8 years ago

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

How Google Maps calculates the shortest distance

Related Stories