为什么Dijkstra的算法不能用于负权重边缘？

Question

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

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

Answer 1

回想一下,在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

编辑更深入的解释:

注意,这很重要,因为在每个放松步骤中,算法假设"闭合"节点的"成本"确实是最小的,因此下一次选择的节点也是最小的.

它的想法是:如果我们有一个打开的顶点使其成本最小 - 通过向任何顶点添加任何正数 - 最小值永远不会改变.
没有正数约束 - 上述假设不正确.

因为我们"知道"每个"闭合"的顶点是最小的 - 我们可以安全地做放松步骤 - 而不是"回头看".如果我们确实需要"回顾" - 贝尔曼 - 福特提供类似递归的(DP)解决方案.

Answer 2

考虑下面显示的图,源为Vertex 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中因此我们再次不进入for循环line16,

所以我们最终得到了距离

注意这是错误的,因为从A到C的最短距离是5 + -10 = -5 .

所以对于这个图,Dijkstra的算法错误地计算从A到C的距离.

这是因为Dijkstra的算法不会尝试找到已经从Q中提取的顶点的较短路径.

什么是line16循环做的是顶点ü,并说:"嘿看起来我们可以去v通过从源头ü,是(ALT或替代)的距离比目前更好DIST [V]我们得到了什么？如果是这样,您更新dist [v] "

请注意,在line16他们检查所有邻居v(即从存在有向边u到v)的ü它们仍然在Q中.在line14他们从Q.删除访问笔记所以,如果X是拜访邻居ü,路径是即使不被认为是从源头上可能更短的方式v.

在上面的例子中,C是B的访问邻居,因此是路径 没有考虑,留下目前最短的路径 不变.

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

所以我说,如果运行此算法时,X是自Q之前提取Ÿ,那么它不可能找到一个路径-这更短.让我用一个例子解释一下,

由于y刚刚被提取并且x已经在其自身之前被提取,所以dist [y]> dist [x]因为否则y将在x之前被提取.(line 13最小距离)

并且因为我们已经假设边缘权重是正的,即长度(x,y)> 0.因此,通过y的替代距离(alt)总是更大,即dist [y] + length(x,y)> dist [x].因此,即使y被视为x的路径,dist [x]的值也不会被更新,因此我们得出结论,只考虑仍然在Q中的y的邻居是有意义的(注意注释)line16

但这个事情取决于我们对正边长的假设,如果长度(u,v)<0则取决于我们可能在比较之后替换dist [x]的负边缘line18.

因此,如果在所有顶点v之前移除x而使得我们所做的任何dist [x]计算都是不正确的- 使得x是v的邻居,其中负边连接它们 - 被移除.

因为这些v顶点中的每一个都是从源到x的潜在"更好"路径上的倒数第二个顶点,这被Dijkstra算法丢弃.

所以在我上面给出的例子中,错误是因为在删除B之前删除了C.而那个C是B的邻居,有一个负边缘!

只是为了澄清,B和C是A的邻居.B有一个邻居C,C没有邻居.length(a,b)是顶点a和b之间的边长.

Answer 3

Dijkstra的算法假定路径只能变得"更重",所以如果你有一条从A到B的路径,权重为3,路径从A到C的权重为3,那么你就无法添加边缘和从A到B到C,重量小于3.

该假设使算法比必须考虑负权重的算法更快.

Answer 4

Dijkstra 算法假设所有边都是正权重，这种假设有助于算法比其他考虑负边可能性的算法运行得更快（ O(E*log(V) ）（例如，复杂度为 O(V^ 的贝尔曼福特算法） 3））。

在以下情况下（带有 -ve 边），其中 A 是源顶点，该算法不会给出正确的结果：

这里，从源 A 到顶点 D 的最短距离应该是 6。但是根据 Dijkstra 方法，最短距离将为 7，这是不正确的。

此外，即使存在负边， Dijkstra 算法有时也可能给出正确的解决方案。以下是此类情况的示例：

然而，它永远不会检测到负循环，并且如果从源可以到达负权循环，则总是产生一个总是不正确的结果，因为在这种情况下，图中不存在从源顶点开始的最短路径。

Answer 5

在下图上尝试 Dijkstra 算法，假设A是源节点，D是目的地，看看发生了什么：

请注意，您必须严格遵循算法定义，而不应该遵循您的直觉（它告诉您上面的路径较短）。

这里的主要观点是，该算法只查看所有直接连接的边，并采用这些边中的最小边。该算法不会向前看。您可以修改此行为，但它不再是 Dijkstra 算法。

Answer 6

Dijkstra算法的正确性:

我们在算法的任何步骤都有2组顶点.集合A由我们计算最短路径的顶点组成.集合B由剩余的顶点组成.

归纳假设:在每个步骤中,我们将假设所有先前的迭代都是正确的.

归纳步骤:当我们将一个顶点V添加到集合A并将距离设置为dist [V]时,我们必须证明该距离是最佳的.如果这不是最佳的,则必须存在到顶点V的一些具有较短长度的其他路径.

假设这个其他路径经过某个顶点X.

现在,由于dist [V] <= dist [X],因此除了图形具有负边长之外,到V的任何其他路径将至少为dist [V]长度.

因此,对于dijkstra算法来说,边缘权重必须是非负的.