How Google Maps calculates the shortest distance

Re:How Google Maps calculates the shortest distance by osrec on Sunday December 30, 2018 @08:07PM (#18792361)

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"

[ Parent | on HN ]

Re:How Google Maps calculates the shortest distance by throw0u1t on Sunday December 30, 2018 @08:16PM (#18792403)

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

[ Parent | on HN ]

Re:How Google Maps calculates the shortest distance by superwayne on Sunday December 30, 2018 @08:12PM (#18792386)

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.

[ Parent | on HN ]

Re:How Google Maps calculates the shortest distance by osrec on Sunday December 30, 2018 @08:18PM (#18792417)

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.

[ Parent | on HN ]

Re:How Google Maps calculates the shortest distance by jelliclesfarm on Sunday December 30, 2018 @08:18PM (#18792413)

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

[ Parent | on HN ]