dijkstras算法是否按顺序放松最短路径的边缘？
在“Introduction to Algorithms，3rd edition”练习24.3-5中想要一个例子，这是错误的（并非总是如此）。 那可能吗？ 在我看来，这是不可能的，因为在到当前顶点的路径已经确定的时候，每条边都会放松。
一个字一个字地：
N.教授声称拥有Dijkstra算法正确性的证明。 他声称，Dijkstra算法按照它们出现在路径上的顺序放松图中每条最短路径的边，因此路径松弛属性适用于从源可达的每个顶点。 通过构造一个有向图来显示教授是错误的，其中Dijkstra算法可以放松最短路径的无序边缘。
我认为措辞中的关键词是dijkstra的算法“放松图中每条最短路径的边缘......”
如果存在多条相同成本的最短路径，那就是一个谎言。
考虑这个图：A→B→A→C→B→D→C→D。源是A，目的地是D.每个边权重是1.从A到D有两条路径，和一个通过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） （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）之前应该总是放松。
重点是，结论并非从前提出发，并构建一个反例。 SSSP找到所有最短的路径。 没有理由认为最短路径需要严格排序。 考虑一个树形图。 所有路径也是最短的。 现在，如果我们放松根部，那么边缘就没有特定的顺序。 但是，假设你甚至强加一个。 然后，在放松最接近的非根节点之后，您可能会在第二层有很多很长的边缘。 下一个最接近的根邻居可能会在第二层的那一部分有一堆非常短的出站边缘。 在这种情况下，因为您总是以最短路径顺序放松NODES而不是边缘，所以放松对总路径长度有贡献的边缘比您已经放松的其他边缘快。
链接地址: http://www.djcxy.com/p/35289.html上一篇: Does dijkstras algorithm relax the edges of the shortest path in order?