哪些算法可以计算地图上从A点到B点的方向？

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

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

像Dijkstra的算法这样的图算法将无法工作，因为图非常大。幸运的是，像A

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

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

PS。这个问题是由在在线制图方向上找到古怪之处引起的。与三角形不等式相反，有时Google

Maps认为XZ比使用XYZ中的中间点花费更长的时间并且更远。但是也许他们的步行方向也针对另一个参数进行了优化？

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

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

以在地图公司工作了18个月的人的身份发言，其中包括在路由算法方面的工作…是的，Dijkstra确实可以工作，但有一些修改：

您无需从源头到目标都进行一次Dijkstra的操作，而应从两端开始，并扩展双方直到中间相遇。这消除了大约一半的工作（2 * pi *（r / 2）^ 2 vs pi * r ^ 2）。

为了避免探索源与目的地之间每个城市的后巷，您可以使用几层地图数据：仅包含高速公路的“高速公路”层，仅包含次要街道的“次级”层，依此类推。然后，您仅浏览更详细层的较小部分，并根据需要进行扩展。显然，此描述省略了很多细节，但是您可以理解。

沿着这些路线进行修改，您甚至可以在非常合理的时间范围内进行越野布线。