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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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