为什么 Dijktra 算法需要更新已探索节点的成本？

Question

我正在实现 Dijktra 算法。为此，我使用一个类，即顶点，它定义图形上的点及其边和权重。作为对此的包装，我有一个所谓的“节点”。这只不过是有关顶点和使用什么节点到达该顶点的信息。

我还保留了所有探索过的节点的列表。如果一个节点被探索过，我们就不会费心再次查看它。在我见过的所有实现中，如果发现已探索的顶点低于当前成本，则它会以新的总成本添加回边界。争论的焦点是，如果我们找到一条到节点的新路径比我们最初到达的节点短，我们必须更新成本以反映这一点并再次考虑。

但这怎么可能发生呢？考虑到我们首先使用最短路径扩展节点，我们什么时候会发现自己处于这样一种情况：到节点的新路径比我们已经找到的路径短？

有人可以给我举一个例子，其中需要更新和重新扩展才能获得最短路径吗？

Answer 1

维基百科条目在此 gif 中显示。

我就在你所描述的情况发生的地方暂停了它。从节点 1 到节点 6 直接花费 14，但从 1 到 3 到 6 只需花费 9 + 2。

由于到达邻居的成本可能比第一个探索的选项更低，因此必须探索通过任何邻居的最低成本。