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

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

像Dijkstra算法这样的图算法将无法工作，因为图是巨大的。

这个论点并不一定成立，因为Dijkstra通常不会查看完整的图，而只是一个非常小的子集(图的互联性越好，这个子集就越小)。

对于行为良好的图，Dijkstra实际上可能表现得相当好。另一方面，通过仔细的参数化，A*总是表现得一样好，甚至更好。您是否已经尝试过它对数据的处理方式?

也就是说，我也很有兴趣听听其他人的经历。当然，像谷歌Map搜索这样的突出例子是特别有趣的。我可以想象类似于有向近邻启发式的东西。

我知道OP里的地图是怎么回事了:

用指定的中间点来观察路线:由于那条路不直，这条路线略微向后走。

如果他们的算法不会回溯，它就看不到更短的路线。

作为一个在地图公司工作了18个月的人，其中包括研究路由算法……是的，Dijkstra的方法确实有效，只是做了一些修改:

Instead of doing Dijkstra's once from source to dest, you start at each end, and expand both sides until they meet in the middle. This eliminates roughly half the work (2*pi*(r/2)^2 vs pi*r^2). To avoid exploring the back-alleys of every city between your source and destination, you can have several layers of map data: A 'highways' layer that contains only highways, a 'secondary' layer that contains only secondary streets, and so forth. Then, you explore only smaller sections of the more detailed layers, expanding as necessary. Obviously this description leaves out a lot of detail, but you get the idea.

通过沿着这些路线进行修改，您甚至可以在非常合理的时间范围内完成跨国家路由。

这个问题在过去几年中一直是一个活跃的研究领域。主要思想是对图进行一次预处理，以加快所有后续查询的速度。有了这些附加信息，行程可以很快计算出来。尽管如此，Dijkstra算法仍然是所有优化的基础。

Arachnid描述了双向搜索和基于层次信息的边缘修剪的用法。这些加速技术工作得很好，但最新的算法在任何方面都优于这些技术。使用目前的算法，在大陆公路网上计算最短路径的时间可大大少于1毫秒。快速实现未修改的Dijkstra算法大约需要10秒。

工程快速路线规划算法概述了该领域的研究进展。有关进一步信息，请参阅那篇论文的参考文献。

已知最快的算法不使用数据中关于道路层次状态的信息，即它是高速公路还是本地道路。相反，他们在预处理步骤中计算自己的层次结构，优化以加快路线规划。这种预计算可以用来精简搜索:在Dijkstra算法中，远离起点和目的地的缓慢道路不需要考虑。好处是非常好的性能和结果的正确性保证。

第一个优化的路线规划算法只处理静态道路网络，这意味着图中的边缘具有固定的成本值。这在实践中是不正确的，因为我们想要考虑交通堵塞或车辆相关限制等动态信息。最新的算法也可以处理这些问题，但仍有问题需要解决，研究还在继续。

如果您需要最短路径距离来计算TSP的解，那么您可能对包含源和目的地之间所有距离的矩阵感兴趣。为此，您可以考虑使用高速公路层次结构计算多对多最短路径。请注意，在过去的两年里，这已经通过更新的方法得到了改进。

我对此有了更多的想法:

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

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

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

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

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

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

我以前没有在谷歌或微软或雅虎地图工作过，所以我不能告诉你他们是如何工作的。

然而，我确实为一家能源公司设计了一个定制的供应链优化系统，其中包括为他们的卡车车队提供调度和路由应用程序。然而，我们对路线的标准远比建筑、交通减速或车道封闭的地方更具体。

我们采用了一种称为ACO(蚁群优化)的技术来调度和路线卡车。该技术是一种人工智能技术，应用于旅行推销员问题来解决路由问题。ACO的技巧是基于路由的已知事实构建错误计算，以便图求解模型知道何时退出(当错误足够小时)。

你可以谷歌ACO或TSP找到更多关于这个技术。然而，我没有使用过任何开源AI工具，所以不能推荐一个(尽管我听说SWARM非常全面)。

Probably similar to the answer on pre-computed routes between major locations and layered maps, but my understanding is that in games, to speed up A*, you have a map that is very coarse for macro navigation, and a fine-grained map for navigation to the boundary of macro directions. So you have 2 small paths to calculate, and hence your search space is much much smaller than simply doing a single path to the destination. And if you're in the business of doing this a lot, you'd have a lot of that data pre-computed so at least part of the search is a search for pre-computed data, rather than a search for a path.

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

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

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

k是一个大于0的常数。

我有点惊讶这里没有提到Floyd Warshall的算法。这个算法很像Dijkstra算法。它还有一个很好的特性，那就是它允许你计算，只要你想继续允许更多的中间顶点。因此，它自然会很快找到使用州际公路或高速公路的路线。

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

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

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

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

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

http://tom.mapsforge.org/

I was very curious about the heuristics used, when a while back we got routes from the same starting location near Santa Rosa, to two different campgrounds in Yosemite National Park. These different destinations produced quite different routes (via I-580 or CA-12) despite the fact that both routes converged for the last 100 miles (along CA-120) before diverging again by a few miles at the end. This was quite repeatable. The two routes were up to 50 miles apart for around 100 miles, but the distances/times were pretty close to each other as you would expect.

唉，我无法重现——算法肯定已经改变了。但这让我对算法很好奇。我所能推测的是，有一些方向修剪，恰好对从远处看的目的地之间的微小角度差异非常敏感，或者有不同的最终目的地选择的预先计算的片段。

我已经在路由方面工作了几年，最近由于客户的需求而引起了大量的活动，我发现a *很容易就足够快了;真的没有必要去寻找优化或更复杂的算法。在一个巨大的图上路由不是问题。

但是速度取决于整个路由网络，我指的是在内存中分别表示路由段和节点的有向图。主要的时间开销是创建这个网络所花费的时间。基于一台运行Windows系统的普通笔记本电脑，并在整个西班牙进行路由的一些粗略数字:创建网络所需时间:10-15秒;计算路线所花费的时间:太短而无法测量。

The other important thing is to be able to re-use the network for as many routing calculations as you like. If your algorithm has marked the nodes in some way to record the best route (total cost to current node, and best arc to it) - as it has to in A* - you have to reset or clear out this old information. Rather than going through hundreds of thousands of nodes, it's easier to use a generation number system. Mark each node with the generation number of its data; increment the generation number when you calculate a new route; any node with an older generation number is stale and its information can be ignored.

就静态道路网络的查询时间而言，目前最先进的技术是Abraham等人提出的Hub标签算法http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20。最近，微软技术报告http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf发布了一份关于该领域的全面而出色的调查报告。

简短的说法是……

Hub标签算法为静态道路网络提供了最快的查询，但需要大量ram来运行(18 GiB)。

传输节点路由稍慢，不过它只需要大约2 GiB的内存，并且有更快的预处理时间。

收缩层次结构在快速预处理时间、低空间需求(0.4 GiB)和快速查询时间之间提供了一个很好的平衡。

没有一种算法是完全占主导地位的……

彼得·桑德斯的谷歌科技演讲可能会让你感兴趣

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

还有Andrew Goldberg的演讲

https://www.youtube.com/watch?v=WPrkc78XLhw

压缩层次结构的开源实现可从KIT的Peter Sanders研究小组网站获得。http://algo2.iti.kit.edu/english/routeplanning.php

还有一篇微软写的关于CRP算法用法的博客文章…http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

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

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

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

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

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

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

地图从不考虑整个地图。 我猜是:- 1. 根据你的位置，它们加载一个地方和那个地方的地标。 2. 当你搜索目的地时，他们会加载地图的另一部分，然后用两个地方做一个图，然后应用最短路径算法。

此外，还有一个重要的技术动态规划，我怀疑是用在最短路径的计算。你也可以参考一下。

全对最短路径算法将计算图中所有顶点之间的最短路径。这将允许预先计算路径，而不需要每次寻找源和目的地之间的最短路径时都计算路径。Floyd-Warshall算法是一种全对最短路径算法。