dijkstras算法是否按顺序放宽最短路径的边缘？

Question

在"算法简介,第3版"练习24.3-5中想要一个例子,这是错误的(并非总是如此).那可能吗？在我看来,这是不可能的,因为在已经确定当前顶点的路径时,每个边都放松了.

一字一字:

N. N.教授声称有一个Dijkstra算法正确性的证明.他声称Dijkstra算法按照它们在路径上出现的顺序放宽图中每条最短路径的边缘,因此路径松弛属性适用于从源可到达的每个顶点.通过构建有向图来显示教授是错误的,Dijkstra的算法可以无序地放松最短路径的边缘.

Answer 1

考虑以下有向图:(A,B),(A,C),(B,D),(C,D),(D,E)边权重w(A,B)= 1,w(A ,C)= 1,w(B,D)= 0,w(C,D)= 0,w(D,E)= 1.源顶点是A.在Dijkstra算法中放松的边缘的可能排列是(A,B),(A,C),(B,D),(D,E),(C,D).此外,在执行Dijkstra算法后,Ad = 0,Bd = 1,Cd = 1,Dd = 1,Ed = 2.从A到E有两条最短的路径,一条是ABDE,另一条是ACDE.矛盾是第二条路径,边缘(C,D)应始终放松(D,E).

Answer 2

我认为措辞中的关键短语是迪杰斯特拉算法“放松了每个 shortest path in the graph..."

如果存在多条成本相同的最短路径，那么这本身就是一个谎言。

考虑这个图：A -> B，A -> C，B -> D，C -> D。源是 A，目标是 D。每条边的权重都是 1。从 A 到 D 有两条路径，一条经过 B然而，一条边 B->D 或 C->D 永远不会放松。

仍然不相信，因为 dijkstra 在将另一条边评估为 D 之前就终止了？添加额外的边 D->E，并将目的地设置为 E。从 A->D 到 B 的路径与 A->D 到 C 的成本相同，并且它们都比从 A->E 的成本便宜。然而，您永远不会将第二条边松弛到 D 中，因为该算法仅将边松弛到它尚不知道到达的最短路径的顶点。