地图提供商（例如Google或Yahoo! Maps）如何建议方向？

我的意思是，他们可能具有某种形式的现实世界数据，当然包括距离，还可能包括行车速度，人行道的存在，火车时刻表等。但是，假设数据采用的是一种简单的格式，例如一个非常大的有向图边缘权重反映距离。我希望能够快速计算从一个任意点到另一点的方向。有时这些点会很靠近（在一个城市内），而有时它们会很远（越野）。

像Dijkstra的算法这样的图算法将无法工作，因为图非常大。幸运的是，像A
*这样的启发式算法可能会起作用。但是，我们的数据非常结构化，也许某种分层方法可能有效？（例如，存储相距很远的某些“关键”点之间的预先计算的方向以及一些本地方向。然后，两个遥远点的方向将涉及到关键点的本地方向，到另一个关键点的全局方向，然后是本地再次指示。）

实际上实际使用哪些算法？

PS。这个问题是由在在线制图方向上找到古怪之处引起的。与三角形不等式相反，有时Google
Maps认为XZ比使用XYZ中的中间点花费更长的时间并且更远。但是也许他们的步行方向也针对另一个参数进行了优化？

PPS。这是对三角形不等式的另一种违反，对我而言，这暗示了他们使用某种分层方法：XZ与XYZ。前者似乎使用了著名的塞巴斯托波尔大道，尽管有点偏离。

编辑 ：这些示例似乎都无法正常工作，但在原始帖子发布时都可以。