sun*_*cat 5 algorithm graph dijkstra shortest-path
在证明Dijkstra算法的正确性时，有一个引理如下：
\n\n\n\n\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)。
\n\n是否存在 d(u) \xe2\x89\xa0 \xce\xb4(s,u) 但 P: s->...->u->v 是从 s 到 v 最短的情况？如果是的话，有人可以在这里举个例子吗？
\n\n任何帮助将不胜感激。
\n小智 0
是的，我们必须需要这个引理。当我们运行算法时，到 u 的距离不断变化，直到我们得到到 u 的最短距离。例如，如果某个节点 a 到达 u，并且通过 a 从 s 到 u 的距离是 d(u) 但不是最优的，并且在算法的后面。我们发现从 s 经 b 到 u 是最短路径。所以此时d(u)就成为最优的。
希望这可以帮助。