13

在“算法简介，第 3 版”练习 24.3-5 中想要一个例子说明这是错误的（并不总是正确的）。那可能吗？在我看来，这是不可能的，因为在已经确定了到当前顶点的路径时，每条边都会放松。

一个字一个字地：

N. 教授声称拥有 Dijkstra 算法正确性的证明。他声称 Dijkstra 的算法按照它们在路径上出现的顺序松弛了图中每条最短路径的边，因此路径松弛特性适用于从源可到达的每个顶点。证明教授错误地构造了一个有向图，Dijkstra 的算法可以针对该有向图放宽最短路径的边缘无序。

4

5 回答 5

12

考虑以下有向图：(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）之前放松。

于 2013-03-04T11:22:27.687 回答
4

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

如果有多个相同成本的最短路径，仅此一项就是谎言。

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

仍然不相信，因为 dijkstra 在将另一边评估为 D 之前终止？折腾一条额外的边 D->E 并将 Destination 设置为 E。从 A->D 到 B 的路径与 A->D 到 C 的成本相同，它们都比从 A->E 的成本便宜。但是，您永远不会将第二条边松弛到 D 中，因为该算法只会将边松弛到它还不知道最短路径的顶点。

于 2011-11-10T04:49:21.600 回答
2

关键是结论不是从前提得出的，要构造一个反例。SSSP 查找所有最短路径。没有理由需要以严格的顺序找到最短路径。考虑一个树形图。所有路径也是最短的。现在，如果我们放松根，那么边上就没有特定的排序。但假设你甚至强加了一个。然后在放松最近的非根节点之后，您可能会有一堆非常长的边到第二层。下一个最近的根邻居可能有一堆非常短的出站边缘到第二层的那个部分。在这种情况下，您将松弛有助于总路径长度的边比您已经松弛的其他边短，因为您总是以最短路径顺序松弛节点，而不是边。

于 2010-09-30T02:14:25.500 回答
1

考虑图表：

    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) 之后松弛。

于 2013-11-26T06:38:10.513 回答
0

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

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

于 2010-09-19T03:38:09.213 回答