有人能告诉我为什么 Dijkstra 的单源最短路径算法假设边必须是非负的。
我说的只是边,而不是负权重循环。
最佳答案
回想一下在 Dijkstra 的算法中,一旦一个顶点被标记为“封闭”(并且不在开放集中)- 算法找到了到它的最短路径,并且永远不必开发这个再次节点 - 它假定开发到此路径的路径是最短的。
但是对于负权重——这可能不是真的。例如:
A
/ \
/ \
/ \
5 2
/ \
B--(-10)-->C
V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}
来自A的Dijkstra会先开发C,后来找不到A->B->C
编辑更深入的解释:
请注意,这很重要,因为在每个松弛步骤中,算法都假设“封闭”节点的“成本”确实是最小的,因此接下来要选择的节点也是最小的。
它的想法是:如果我们有一个开放的顶点,那么它的成本是最小的 - 通过将任何 正数 添加到任何顶点 - 最小性永远不会改变。
没有对正数的约束——上述假设不成立。
因为我们确实“知道”每个“闭合”的顶点都是最小的——我们可以安全地进行松弛步骤——而不用“回头看”。如果我们确实需要“回头看” - Bellman-Ford为此提供了类似递归 (DP) 的解决方案。
关于algorithm - 为什么 Dijkstra 算法不适用于负权重边?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13159337/