最近我有一个工作面试，他们问我“谷歌地图使用哪种方法来找到两个城市之间的最短路径？”。我没有那个问题的答案，但我猜他们使用“最短路径算法”来寻找路径，但面试官说“不”。在那次采访之后，我用谷歌搜索了很多，但没有找到任何方法。如果您对谷歌地图如何找到两个城市之间的最短路径有任何想法，请告诉我
问问题
15192 次
2 回答
1
碰巧我刚刚参加了一个关于它的演讲。Dijkstras 算法对谷歌来说效率太低了。虽然复杂度 n log n 很好，但它所花费的绝对时间非常大。
Google 使用Contraction Hierarchies的变体。它比 Dijkstra 更快，因为网络是经过预处理的。尽管有更快的算法涉及预处理，但 CH 提供了很大的灵活性。
于 2017-07-07T14:33:40.147 回答
0
A*呢？它似乎适合寻路。
于 2015-01-09T09:20:53.020 回答