您刚刚在手机上的导航软件中输入了目标地址。它计算它认为需要最短时间的路线。
当您开车时，您会遇到一些GPS漂移，导航软件认为您已经在高速公路上下了匝道。
我想知道从算法的角度来看，导航软件在一秒钟后估计出更准确的位置时如何知道自我纠正？这个问题可能看起来很简单，但我正在寻找一个非常具体的答案。
我猜该应用程序在几个节点的内存中存储了一个图形，这些节点描绘了不同的道路位置(这也是为了它知道如何在正确的方向上绘制一条线(。当它猜测你在出口匝道退出时，它会意识到你与它认为你去过的节点的估计距离太远而不准确，所以它在图表上回溯并走另一条路并找到正确的节点。这是对的吗？还是更简单？它是否会返回DFS，直到找到最接近您当前位置的节点？
市面上有很多不同的导航系统，它们使用不同的算法，所以我怀疑能有一个普遍的答案，但是：
快速导航的典型"教科书"方法是双面略微修改的Dijkstra。换句话说，你从头开始，用你到达那里所需的时间和你来自的节点标记所有直接连接的节点。
然后，对连接到这些节点的节点重复此操作。冲洗，重复。如果您遇到以前见过的节点，您可以将到达该站点所需的时间与那里已经标记的路径进行比较。只有较短的幸存下来。
你交替地这样做，从你的起点和你的目的地。(你可以有点聪明——例如，你很少会在小路上朝错误的方向走 50 公里(。在某些时候，两棵树"相遇"。你基本上可以在你发现可以从两端到达的所有节点之间做一个图切割，并使用穿过最短距离节点的路径。
现在，回到你的问题：你的导航系统发现你走了一条它没想到你会走的路。没问题，该节点只能是直接连接到您所在的节点——其他节点不太可能，除非你可以传送。现在，如上所述，由于Dijkstra已经计算了到达该节点所需的时间，因此只需旋转树即可。真的，如果你正在做路线规划，这是非常标准的策略。
所以，你有有趣的问题！我建议，如果你还没有，你读一下Dijkstra的算法。