google-maps - 谷歌地图使用算法/方法寻找两个城市之间的路径

Question

最近我有一个工作面试，他们问我“谷歌地图使用哪种方法来找到两个城市之间的最短路径？”。我没有那个问题的答案，但我猜他们使用“最短路径算法”来寻找路径，但面试官说“不”。在那次采访之后，我用谷歌搜索了很多，但没有找到任何方法。如果您对谷歌地图如何找到两个城市之间的最短路径有任何想法，请告诉我

Answer 1

碰巧我刚刚参加了一个关于它的演讲。 Dijkstras 算法对谷歌来说效率太低了。虽然复杂度 n log n 很好，但它所花费的绝对时间非常大。

Google 使用 Contraction Hierarchies 的变体.它比 Dijkstra 更快，因为网络是经过预处理的。尽管有更快的算法涉及预处理，但 CH 提供了很大的灵 active 。