为什么不Dijkstra的负重量边缘算法的工作？(Why doesn't Dijkstra&

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

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

Answer 1:

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

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

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

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

Dijkstra算法从A将首先开发C，稍后会无法找到A->B->C

编辑深一点的解释：

请注意，这是很重要的，因为在每个松弛工序中，算法假定“成本”到“封闭”节点确实是最小的，因此，下一个将要选择的节点也微乎其微。

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

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

Answer 2:

考虑与源如下所示的图形作为顶点A.首先尝试在其上运行的Dijkstra算法自己。

当我提到Dijkstra算法在我的解释，我将谈论的Dijkstra算法如下实施，

这样开始了的值最初被分配给每个顶点是（ 在从源到顶点的距离 ），

我们首先提取在Q上的顶点= [A，B，C]，其具有最小的值，即A，之后，Q = [B，C]。 注意A具有向边以B和C，也两者都是在Q，因此我们更新两个这些值，

现在我们提取C作为（2 <5），现在Q = [B]。 需要注意的是C连接到什么都没有，所以line16循环不运行。

最后，我们提取物B，之后，。注意B有向边至C，但C是不存在Q中，因此我们再次没有进入中环路line16 ，

所以，我们最终的距离为

注意这是怎么错了，因为从A到C的最短距离是5 + -10 = -5，当你去。

因此，对于这个图Dijkstra算法错误计算从A到C的距离

这是因为Dijkstra算法并不试图找到其已经自Q提取顶点较短的路径。

什么line16循环做的是顶点u和说：“嘿，看起来我们可以通过u去到v从源代码，是（ALT或替代）的距离比目前的DIST [V]我们还有更好的吗？如果这样可以让更新DIST [v]“

请注意，在line16他们检查所有邻居V（即从u存在到v的有向边），U的它仍然在Q值 。在line14他们remove从Q.访问笔记所以如果x为u的被访问邻居，路径 甚至不被认为是从源到v可能更短的方式。

在上面的例子中，C为B的访问邻居，从而该路径没有考虑，离开当前的最短路径不变。

这实际上是有用的，如果边缘的权重都为正数 ，因为那样的话我们就不会浪费我们的时间考虑路径不能缩短 。

所以我说，如果X是自Q 在y之前提取运行该算法时，那么它不可能找到一个路径- 这是较短的。让我用一个例子来说明这一点，

为Y刚刚被提取和X已经提取自己之前，则DIST [Y]> DIST [X]，否则y还得到X之前提取。（ line 13分钟距离第一）

正如我们已假设边缘权重是正的，即长度（X，Y）> 0。 所以经由y中的替代距离（ALT）总是一定要更大，即DIST [Y] +长度（X，Y）> DIST [X]。 所以DIST的值[X]就不会被更新，甚至如果y被视为对x的路径，因此，我们得出结论，是有意义的只考虑Y的邻居，其仍然在Q（在附注注释line16 ）

但是这件事情取决于我们正沿长度的假设，如果长度（U，V）<0，则取决于如何负即边缘是我们可以在比较之后更换DIST [X] line18 。