这纯粹是我的猜测，但我认为他们可能会使用覆盖有向图的影响图数据结构，以缩小搜索域。这将允许搜索算法在所需行程较长时将路径导向主要路线。

鉴于这是一个谷歌应用程序，我们也可以合理地假设，许多神奇的功能都是通过大量缓存完成的。如果缓存前5%最常见的谷歌地图路由请求，我不会感到惊讶(20%?50%?)的请求需要通过简单的查询来回答。

以下是世界上最快的路由算法的比较和正确性:

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

下面是谷歌关于这个主题的技术演讲:

http://www.youtube.com/watch?v=-0ErpE8tQbw

以下是schultes所讨论的高速公路层次算法的实现(目前仅在柏林，我正在编写界面，移动版本也正在开发中):

http://tom.mapsforge.org/

说到GraphHopper， 一个基于OpenStreetMap的快速开源路线规划器，我阅读了一些文献并实现了一些方法。最简单的解决方案是Dijkstra，一个简单的改进是双向Dijkstra，它大致只探索一半的节点。在双向Dijkstra模式下，穿越整个德国需要1秒(汽车模式)，在C模式中可能只需要0.5秒左右;)

我在这里用双向Dijkstra创建了一个真实路径搜索的动图。还有一些想法可以让Dijkstra更快，比如做A*，这是一个“面向目标的Dijkstra”。我还为它创建了一个gif动画。

但是怎样才能(快得多)呢?

问题是，对于路径搜索来说，必须探索位置之间的所有节点，这是非常昂贵的，因为在德国已经有数百万个节点了。但是Dijkstra等的另一个痛点是这样的搜索使用大量的RAM。

有启发式解决方案，也有精确解决方案，将图(路网)分层组织，两者都有优缺点，主要解决速度和RAM问题。我在这个回答中列出了其中的一些。

对于GraphHopper，我决定使用收缩层次结构，因为它相对“容易”实现，并且不需要花时间来准备图表。它仍然会导致非常快的响应时间，就像你可以在我们的在线实例GraphHopper Maps上测试一样。例如，从南非到中国东部，距离23000公里，汽车行驶时间近14天，在服务器上只需要0.1秒。

事实上，我已经做过很多次了，尝试了几种不同的方法。根据地图的大小(地理位置)，您可能会考虑使用haversine函数作为启发式方法。

我的最佳解决方案是使用带有直线距离的A*作为启发式函数。但接下来你需要地图上每个点(交集或顶点)的某种坐标。您还可以为启发式函数尝试不同的权重，即。

f(n) = k*h(n) + g(n)

k是一个大于0的常数。

只是解决三角形不等式的违反，希望他们优化的额外因素是常识。你不一定想要最短或最快的路线，因为这可能会导致混乱和破坏。如果你想让自己的路线更适合卡车行驶，并且能够应对每个卫星导航跟踪司机都沿着这些路线行驶的情况，那么你很快就可以放弃三角形不等式[1]。

如果Y是X和Z之间的一条狭窄的住宅街道，那么您可能只想在用户明确要求X-Y-Z时使用通过Y的快捷方式。如果他们要求X-Z，他们应该坚持走主干道，即使它有点远，需要更长的时间。这类似于Braess悖论——如果每个人都试图选择最短、最快的路线，那么随之而来的拥堵意味着这条路线不再是任何人最快的路线。从这里开始，我们将从图论转向博弈论。

事实上，当你允许单向道路并失去对称性要求时，任何产生的距离将是数学意义上的距离函数的希望都将破灭。失去三角不等式也只是在伤口上撒盐。

我对此有了更多的想法:

1)记住地图代表一个实体组织。存储每个交叉口的经纬度。除了目标方向上的点以外，你不需要检查太多。只有当你发现自己受阻时，你才需要超越这一点。如果你储存了大量的高级连接，你就可以进一步限制它们——通常情况下，你永远不会以偏离最终目的地的方式穿过其中任何一个连接。

2)根据有限的连通性将世界划分为一系列区域，定义区域之间的所有连通性点。找出您的源和目标所在的区域，从您的位置到每个连接点的起始和结束区域路由，以及连接点之间的区域映射。(我怀疑后者在很大程度上是事先计算好的。)

请注意，区域可以比大都市区域小。任何具有地形特征的城市(比如一条河)都是多个区域。