为什么 Dijkstra 的算法对负权重边缘不起作用？

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

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

234407 次浏览
小开

Dijkstra 的算法假设路径只能变得“更重”，所以如果你有一条权重为3的从 A 到 B 的路径，和一条权重为3的从 A 到 C 的路径，那么你就不可能添加一条边，并且在权重小于3的情况下从 A 到 B 到 C。

这种假设使得算法比那些必须考虑负权重的算法更快。

小开
最佳答案

回想一下，在 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)的解决方案。

小开

在下面的图中尝试 Dijkstra 的算法，假设 A是源节点，D是目标节点，看看发生了什么:

Graph

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

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

小开

Dijkstra 算法的正确性:

在算法的任意一个步骤中，我们都有两组顶点。集合 A 由我们计算出最短路径的顶点组成。集合 B 由剩余的顶点组成。

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

归纳步骤 : 当我们给集合 A 增加一个顶点 V 并将距离设置为 dist [ V ]时，我们必须证明这个距离是最优的。如果这不是最佳的，那么必须有一些其他路径的顶点 V 是较短的长度。

假设另一条路径通过某个顶点 X。

现在，由于 dist [ V ] < = dist [ X ] ，因此到 V 的任何其他路径都至少是 dist [ V ]长度，除非图的边长是负的。

因此，为了使 dijkstra 算法有效，边权必须是非负的。

小开

考虑下面显示的图，源代码为顶点 A。首先尝试自己在上面运行 Dijkstra 的算法。

enter image description here

当我在解释中提到 Dijkstra 的算法时，我将讨论下面实现的 Dijkstra 算法,

Dijkstra’s algorithm

从最初分配给每个顶点的 价值观(从源头到顶点的距离)开始,

initialization

我们首先提取 Q = [ A，B，C ]中具有最小值的顶点，即 A，然后提取 Q = [ B，C ]。注意 A 对 B 和 C 有一个有向边，而且它们都在 Q 中，因此我们更新这两个值,

first iteration

现在我们提取 C 为(2 < 5) ，现在提取 Q = [ B ]。请注意，C 没有连接到任何东西，所以 line16循环不会运行。

second iteration

最后提取 B，然后提取 < img src = “ https://i.stack.imgur.com/s2ono.png”alt = “ Q is Phi”> < img src = “ https://i.stack.imgur.com/s2ono.png”alt = “ Q is Phi”> 。注意 B 有一个指向 C 的边，但是 C 在 Q 中不存在，因此我们再次不在 line16中输入 for 循环,

3rd?

所以我们得到的距离是

no change guys

注意这是错误的，因为当你走 < img src = “ https://i.stack.imgur.com/coJUT.png”alt = “ a to b to c”> < img src = “ https://i.stack.imgur.com/coJUT.png”alt = “ a to b to c”> 时，从 A 到 C 的最短距离是5 + -10 = -5。

因此 Dijkstra 的算法错误地计算了从 A 到 C 的距离。

这是因为 Dijkstra 的算法没有尝试找到到 已经从 Q 中提取出来了顶点的更短路径。

line16循环所做的就是获取顶点 你，然后说: “嘿，看起来我们可以通过 你从源进入到 < strong > v ，这个(alt 或者替代)距离是否比我们得到的当前的 < strong > dist [ v ] 要好？如果是这样，那么让 update < strong > dist [ v ] “

注意，在 line16中，它们检查 你的所有相邻 翻译(即 从 u 到 v中存在有向边) ，即 还在 Q 区。在 line14中，他们从 Q 中删除已访问的笔记。因此，如果 X是 你的访问邻居，路径 < img src = “ https://latex.codecogs.com/gif.latex? source & space;% 5Cto & space;% 5Cto & space;% 5Cto & space; v”alt = “ source to u to x”>是 甚至都没考虑过，作为从源到 翻译的一条可能较短的路径。

在上面的例子中，C 是 B 的一个访问邻居，因此路径 < img src = “ https://latex.codecogs.com/gif.latx? A & space;% 5Cto & space;% 5Cto & space; C”alt = “ A to B to C”> 未被考虑，保留当前最短路径 < img src = “ https://latex.codecogs.com/gif.latx? A & space;% 5Cto & space; C”alt = “ A to C”> 不变。

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

所以我说当运行这个算法时，如果 X是在 嘿之前从 Q 中提取出来的，那么就不可能找到一个更短的路径-< img src = “ https://i.stack.imgur.com/OjAzQ.png”alt = “ not could”> < img src = “ https://i.stack.imgur.com/OjAzQ.png”alt = “ not could”> 。让我用一个例子来解释一下,

因为 嘿是刚刚提取的，而 X是在它之前提取的，那么 Dist [ y ] > dist [ x ]是因为否则 嘿就会在 X之前被提取。(line 13分钟距离第一)

正如我们已经知道的 假设，边权是正的，也就是 长度(x，y) > 0。因此，通过 嘿的替代距离(alt)总是肯定会更大，即 Dist [ y ] + length (x，y) > dist [ x ]。因此，即使 嘿被认为是 X的路径，[ x ]的值也不会被更新，因此我们得出结论，只考虑仍然在 Q 中的 嘿的邻居是有意义的(注意 line16中的注释)

但这取决于我们对正边长的假设，如果 长度(u，v) < 0取决于边长的负值，我们可以在 line18比较后替换 [ x ]。

因此，如果在去掉所有顶点 翻译之前去掉 X，那么我们所做的任何 [ x ]计算都是不正确的——例如，X是 翻译的一个负边连接它们的邻居。

因为每个 翻译顶点都是从源到 X的潜在“更好”路径上的倒数第二个顶点，这被 Dijkstra 的算法丢弃了。

所以在我上面给出的例子中，错误是因为在 B 被删除之前 C 被删除了。而那个 C 是 B 的一个负边的邻居！

澄清一下，B 和 C 是 A 的邻居。B 只有一个邻居 C，而 C 没有邻居。Length (a，b)是顶点 a 和 b 之间的边长。

小开

回想一下 Dijkstra 的算法，一旦一个顶点被标记为“闭合”(并且超出了开集)-它假设任何从它发出的节点都会导致更远的距离，算法找到了通向它的最短路径，并且永远不必再开发这个节点，但是在负权值的情况下这不成立。

小开

到目前为止的其他答案很好地说明了为什么 Dijkstra 的算法不能处理路径上的负权重。

但问题本身可能是基于对路径重量的错误理解。如果路径上的负权在寻路算法中通常是允许的，那么您将得到不会停止的永久循环。

想想这个:

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

A 和 D 之间的最佳路径是什么？

任何寻路算法都必须在 B 和 C 之间不断循环，因为这样做会减少总路径的权重。因此，对连接允许负权值会使任何寻路算法失去意义，也许除非您将每个连接限制为只使用一次。

因此，为了更详细地解释这一点，请考虑以下路径和权重:

Path               | Total weight
ABCD               | 9
ABCBCD             | 7
ABCBCBCD           | 5
ABCBCBCBCD         | 3
ABCBCBCBCBCD       | 1
ABCBCBCBCBCBCD     | -1
...

那么，什么是最佳路径呢? 算法每增加一个 BC步骤，总重量就减少2。

因此最佳路径是 A (BC) D，BC部分永远循环。

由于 Dijkstra 的目标是找到最优路径(而不是任何路径) ，根据定义，它不能使用负权，因为它不能找到最优路径。

Dijkstra 实际上不会循环，因为它保留了一个它访问过的节点列表。但它不会找到一个完美的路径，而是只是任何路径。

小开

您可以使用 dijkstra 的算法与负边不包括负周期，但您必须允许一个顶点可以访问多次，该版本将失去它的快速时间复杂度。

在这种情况下，实际上我已经看到它更好地使用 SPFA 算法有正常的队列，可以处理负边。

小开

Dijkstra 的算法 假设所有的边都是正加权的，这个假设有助于算法运行得更快(O (E * log (V))比其他算法更考虑到负边的可能性(例如 Bellman ford 的算法具有 O (V ^ 3)的复杂性)。

这个算法不会给出正确的结果在下面的情况下(与一个-ve 边) ，其中 A 是源顶点:

enter image description here

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

还有 Dijkstra 的算法 即使有负边 ，有时也会给出正确的解，下面是这种情况的一个例子:

enter image description here

但是，它永远不会检测到负面循环和 总是产生一个结果，如果是 负重循环可从源头到达，它们总是 < strong > 不正确 ，因为在这种情况下，从源顶点到图中不存在最短路径。

小开

在前面答案的基础上，为下面的简单例子增加几点解释,

enter image description here

  1. Dijktra 的算法是贪婪的，它首先贪婪地找到距离源点 A的最小距离点 C，然后将距离 D [ C ](距离 A)分配给边 空调的权重。
  2. 基本的假设是，由于 C是第一个被选中的，因此在图 s.t. W (AV) < w (AC)中没有其他的顶点 V，否则算法就会选中 V而不是 C。
  3. 由于以上逻辑，W (AC) < = w (AV)，对于所有的顶点 V不同于顶点 A和 C。现在，很明显，任何从 A开始并以 C结束的路径，经过 V，即路径 P = A-> V-> ...-> C，其长度将会更长(> = 2) ，路径 P的总成本将是它上面的边的和，即，假设 P上的所有边都有 V2，因此 C 可以安全地从队列 问:中删除，因为在这种假设下，D [ C ]不可能进一步变小/放松。
  4. 显然，当 P上的 some. edge 为负时，上述假设不成立，在这种情况下，D [ C ]可能会进一步减少，但是算法不能处理这种情况，因为到那时它已经从队列 问:中删除了 C。

提交答案