Google Maps用于查找两个城市之间路径的算法/方法
Google Maps用于查找两个城市之间路径的算法/方法
提问于 2012-12-30 21:56:00
最近我参加了一次求职面试，他们问我“谷歌地图使用哪种方法来寻找两个城市之间的最短路径？”我不知道这个问题的答案，但我猜他们使用“最短路径算法”来寻找路径，但面试官说“不”。在那次面试之后，我用谷歌搜索了很多，但没有找到任何方法。如果您对google地图如何找到两个城市之间的最短路径有任何想法，请告诉我
回答 2
Stack Overflow用户
发布于 2017-07-07 22:33:40
碰巧我刚刚参加了一个关于它的讲座。Dijkstras算法对google来说效率太低。虽然复杂度n log n很好，但所需的绝对时间相当长。
谷歌使用的是Contraction Hierarchies的一个变体。它比Dijkstra更快，因为网络经过了预处理。即使有涉及预处理的更快的算法，CH也提供了很大的灵活性。
Stack Overflow用户
发布于 2015-01-09 17:20:53
那A*呢？它似乎适合于路径查找。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14091279
复制相关文章
相似问题
腾讯云开发者
