algorithm - 对 Dijkstra 算法的证明感到困惑

Question

在 Dijkstra 算法正确性的证明中，有一个引理说明如下:

Let u be v's predecessor on a shortest path P: s->...->u->v from s to v. Then, If d(u) = δ(s,u) and edge (u, v) is relaxed, we have d(v) = δ(s,v), where funciton δ(x, y) denotes the minimum path weight from x to y.

我想知道为什么在这个引理中我们需要条件 d(u) = δ(s,u)。如果路径 P: s->...->u->v 是从 s 到 v 的最短路径，那么根据最优子结构的性质，P 的子路径 s->...->u 也必定是一个从 s 到 u 的最短路径。因此，d(u) 必须等于 δ(s,u)。

是否存在 d(u) ≠ δ(s,u) 但 P 的情况:s->...->u->v 是从 s 到 v 的最短路径？如果是这样，有人可以在这里提供一个例子。

任何帮助将不胜感激。

Answer 1

是的，我们必须需要那个引理。
当我们运行算法时，到 u 的距离会发生变化，直到我们得到到 u 的最短距离。例如，如果某个节点 a 到达 u，并且通过 a 从 s 到 u 的距离为 d(u) 但不是最优的，然后在算法中。我们发现从 s 到 u 通过 b 是最短路径。所以在这一点上，d(u) 成为最优的。

希望这可以帮助。