How Google Maps calculates the shortest distance

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 ]