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

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

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

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

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

我对此有了更多的想法:

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

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

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

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.

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

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

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

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

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

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

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

http://tom.mapsforge.org/