为什么不Dijkstra算法工作负重量的边缘？ [英] Why doesn't Dijkstra's algorithm work for negative weight edges?

问题描述

有人可以告诉我为什么Dijkstra算法单源最短路径假定边缘必须是非负的。

Can somebody tell me why Dijkstra's algorithm for single source shortest path assumes that the edges must be non-negative.

我说的只是边缘不是负重量周期。

I am talking about only edges not the negative weight cycles.

推荐答案

回想一下，在Dijkstra算法，一旦顶点被标记为关闭（进出开集的） - 算法找到最短路径它，然后将永远不会再开发这个节点 - 它假定开发这条道路的路径是最短的。

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest.

但随着负权重 - 这可能不是真的。例如：

But with negative weights - it might not be true. For example:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Dijkstra算法从A将首先开发C，稍后会无法找到 A-＆GT; B-＆GT的温度

修改深一点的解释：

请注意，这是重要的，因为在每一个放松步骤中，算法假定的成本，以关闭节点的确是最小的，并且因此下一个将被选择的节点也是最小的。

Note that this is important, because in each relaxation step, the algorithm assumes the "cost" to the "closed" nodes is indeed minimal, and thus the node that will next be selected is also minimal.

它的想法是：如果我们在开这样的顶点，它的成本是最小的 - 通过添加任何的正数的任何顶点 - 在极小永远不会改变。
没有对正数的约束 - 上述假设是不正确的

The idea of it is: If we have a vertex in open such that its cost is minimal - by adding any positive number to any vertex - the minimality will never change.
Without the constraint on positive numbers - the above assumption is not true.

由于我们知道每个顶点这是封闭是最小的 - 我们可以放心地做放松步骤 - 没有回头看。如果我们确实需要回头看 - 贝尔曼 - 福特提供了一个递归式的（DP这样做的）溶液

Since we do "know" each vertex which was "closed" is minimal - we can safely do the relaxation step - without "looking back". If we do need to "look back" - Bellman-Ford offers a recursive-like (DP) solution of doing so.

这篇关于为什么不Dijkstra算法工作负重量的边缘？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！