Dijkstra算法是否按顺序放松最短路径的边？

Question

在《算法导论》（第三版）中，习题24.3-5要求提供一个例子证明这种情况是错误的（不总是正确的）。这可能吗？在我看来，这是不可能的，因为每个边缘在路径到当前顶点已经确定的时候都已被松弛。

逐字翻译：

教授N声称有Dijkstra算法正确性的证明。他声称Dijkstra算法以它们出现在路径上的顺序放松每条最短路径的边缘，因此路径松弛性质适用于从源可达的每个顶点。通过构造一个有向图，展示教授的观点是错误的，即Dijkstra算法可能会以错序的方式放松最短路径的边缘。

- Steinbitglis

---

获取这个练习或一些代码示例。 - Svisstack

这是确切的问题吗？如果不是，请您逐字逐句地发布它。 - IVlad

我的唯一猜测是使用零权重边（因为它们在ITA中被明确允许）。显然，在零边网络中，每条路径都是最短的。 - Nikita Rybak

Answer 1

Consider the following directed graph: (A,B), (A,C), (B,D), (C,D), (D,E) with edge weights w(A,B)=1, w(A,C)=1, w(B,D)=0, w(C,D)=0, w(D,E)=1. The source vertex is A. A possible permutation of edges relaxed in Dijkstra's algorithm is (A,B), (A,C), (B,D), (D,E), (C,D). Besides, A.d=0, B.d=1, C.d=1, D.d=1, E.d=2 after performing Dijkstra's algorithm. There are two shortest paths from A to E, one is ABDE and the other is ACDE. The contradiction is in the second path where edge (C,D) should always be relaxed before (D,E).

- user2131509

---

似乎唯一的情况是某些边的权重为零。在这个例子中，在(A, B)被松弛后，D和C具有相同的值1。如果在C之前选择D，则不会评估(C, D)的松弛。 - jason zhang

Answer 2

我认为措辞中的关键短语是Dijkstra算法"放松图中每条最短路径的边缘..."

如果有多个相同成本的最短路径，则这本身就是一个谎言。

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

还不确定，因为Dijkstra在评估D的其他边缘之前终止？再加入一个额外的边D->E并将目标设置为E。通过B从A->D的路径与通过C从A->D的路径具有相同的成本，并且它们都比从A->E的成本便宜。但是，您永远不会放松第二个边缘进入D，因为该算法仅放松到它尚未知道最短路径的顶点的边缘。

- Nate

---

我不确定是否正确，但我将您的答案标记为解决方案。 - Steinbitglis

@Nate，你的观点：“...算法只放松到其不知道最短路径的顶点”是错误的。每当添加一个顶点时，Dijkstra算法都会放松每条出边。 - raghavsood33

@raghavsood33 听起来没错；当Dijkstra访问一个节点时，它会放松每条出边。我喜欢user2131509的回答。 - Nate

Answer 3

重点是结论并不是由前提得出的，需要构造反例。SSSP可以找到所有最短路径。没有理由要按严格顺序找到最短路径。考虑一棵树形图。所有路径也都是最短的。现在，如果我们放松根节点，那么边缘上就没有特定的排序了。但是假设你甚至强制实施了一个排序。然后在放松最接近的非根节点之后，你可能会有一堆真正长的边到第二层。下一个最近的根邻居可能有一堆真正短的出边到那部分第二层。在这种情况下，你会放松那些对总路径长度贡献更小的边，因为你总是按照最短路径顺序放松节点，而不是边。

- Ian

Answer 4

考虑这个图表：

    A--->B  A--->C  B--->C  C--->D 

让每条边的权重都为0。

Dijkstra算法可以按顺序放松边缘

    (A,C) (A,B) (C,D) (B,C)

图中有两条从A到D的最短路径，都花费0。

    A-->B-->C-->D   or   A-->C-->D

最短路径 {A-->B-->C-->D} 的边缘在松弛时无序，因为 (B,C) 在 (C,D) 之后被松弛。

- Arun Kumar

Answer 5

生成一条单边，权重为三的路径，到达目的地。现在添加一个由多个停靠点组成的路径，总权重小于三，也能到达目的地。当你放松起点时，你会将目标节点着色为三，这是错误的。你必须继续放松所有比（已知最短路径到目的地）更近的节点，直到该集合为空。只有这样，您才可以确定D算法给出了正确的答案。

查找A*算法以获得更多乐趣。

- Ian

---

最短路径的边仍然按顺序被松弛，不是吗？ - Steinbitglis