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

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

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

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

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

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

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

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

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.