地图提供商（比如谷歌或雅虎地图）是如何建议路线的呢？
它们可能有某种形式的真实世界数据，肯定包括距离，但也可能包括行驶速度、人行道存在情况、火车时间表等等。但假设数据以更简单的格式存在，例如一个非常大的有向图，边缘权重反映距离。我想能够快速计算从任意一点到另一点的方向。有时这些点会很近（在同一个城市内），而有时它们会很远（横跨全国）。
像Dijkstra算法这样的图形算法不适用于庞大的图形。幸运的是，启发式算法，如A *算法，可能有效。然而，我们的数据非常结构化，也许一种分层方法可能会起作用？（例如，在某些遥远的“关键”点之间存储预先计算的方向，以及一些本地方向。然后，两个远离的点的方向将涉及到关键点的本地方向，到另一个关键点的全局方向，以及再次的本地方向。）
实际上使用了哪些算法？
附注：此问题的动机是在在线地图方向中发现的异常。与三角不等式相反，有时候Google Maps认为使用一个中间点作为 X-Y-Z 比使用 X-Z 更长更远。但也许他们的步行路线也优化了另一个参数呢？
附注：这里又有一个违反三角不等式的例子，它表明（对我来说）他们使用某种分层方法：X-Z与X-Y-Z。前者似乎使用了显眼的Sebastopol大道，即使它略微偏离了路线。
编辑：这些例子都似乎不再起作用，但在原始帖子发布时，两者都有效。
