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

在“算法简介，第3版”练习24.3-5中想要一个例子，这是错误的（并非总是如此）。那可能吗？在我看来，这是不可能的，因为在已经确定当前顶点的路径时，每个边缘都是松弛的。一字一字： N. N.教授声称有一个Dijkstra算法正确性的证明。他声称Dijkstra算法按照它们在路径上出现的顺序放宽图中每条最短路径的边缘，因此路径松弛属性适用于从源可到达的每个顶点。通过构建有向图来显示教授是错误的，Dijkstra的算法可以无序地放松最短路径的边缘。

已邀请:

5 个回复

呢率篓舍烫

我认为措辞中的关键词是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.从A-> D到B的路径与A-> D到C的成本相同，并且它们都比A-> E的成本便宜。但是，您永远不会将第二条边放宽到D，因为算法只会将边放松到它不知道最短路径的顶点。

茶鬼失形

考虑以下有向图：（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算法后，A.d = 0，B.d = 1，C.d = 1，D.d = 1，E.d = 2。从A到E有两条最短的路径，一条是ABDE，另一条是ACDE。矛盾是第二条路径，边缘（C，D）应始终放松（D，E）。

社攻取墟槽

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