小编sun*_*cat的帖子

在证明Dijkstra算法的正确性时，有一个引理如下：

\n

设 u 是 v 在最短路径 P 上的前驱： s->...->u->v 从 s 到 v。那么，如果 d(u) = \xce\xb4(s,u) 且边 (u, v) 是松弛的，我们有 d(v) = \xce\xb4(s,v)，其中 funciton \xce\xb4(x, y) 表示从 x 到 y 的最小路径权重。

\n

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

是否存在 d(u) \xe2\x89\xa0 \xce\xb4(s,u) 但 P: s->...->u->v 是从 s 到 v 最短的情况？如果是的话，有人可以在这里举个例子吗？

任何帮助将不胜感激。