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

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

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

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

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

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

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

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

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

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.

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.

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

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

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

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

k是一个大于0的常数。

作为一个在地图公司工作了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.

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