algorithm - Why doesn't Dijkstra's algorithm work for negative weight edges?

Question

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.

Answer 1

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 from A will first develop C, and will later fail to find A->B->C

---

EDIT a bit deeper explanation:

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.

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.

Answer 2

Consider the graph shown below with the source as Vertex A. First try running Dijkstra’s algorithm yourself on it.

When I refer to Dijkstra’s algorithm in my explanation I will be talking about the Dijkstra's Algorithm as implemented below,

So starting out the values (the distance from the source to the vertex) initially assigned to each vertex are,

We first extract the vertex in Q = [A,B,C] which has smallest value, i.e. A, after which Q = [B, C]. Note A has a directed edge to B and C, also both of them are in Q, therefore we update both of those values,

Now we extract C as (2<5), now Q = [B]. Note that C is connected to nothing, so line16 loop doesn't run.

Finally we extract B, after which . Note B has a directed edge to C but C isn't present in Q therefore we again don't enter the for loop in line16,

So we end up with the distances as

Note how this is wrong as the shortest distance from A to C is 5 + -10 = -5, when you go .

So for this graph Dijkstra's Algorithm wrongly computes the distance from A to C.

This happens because Dijkstra's Algorithm does not try to find a shorter path to vertices which are already extracted from Q.

What the line16 loop is doing is taking the vertex u and saying "hey looks like we can go to v from source via u, is that (alt or alternative) distance any better than the current dist[v] we got? If so lets update dist[v]"

Note that in line16 they check all neighbors v (i.e. a directed edge exists from u to v), of u which are still in Q. In line14 they remove visited notes from Q. So if x is a visited neighbour of u, the path is not even considered as a possible shorter way from source to v.

In our example above, C was a visited neighbour of B, thus the path was not considered, leaving the current shortest path unchanged.

This is actually useful if the edge weights are all positive numbers, because then we wouldn't waste our time considering paths that can't be shorter.

So I say that when running this algorithm if x is extracted from Q before y, then its not possible to find a path - which is shorter. Let me explain this with an example,

As y has just been extracted and x had been extracted before itself, then dist[y] > dist[x] because otherwise y would have been extracted before x. (line 13 min distance first)

And as we already assumed that the edge weights are positive, i.e. length(x,y)>0. So the alternative distance (alt) via y is always sure to be greater, i.e. dist[y] + length(x,y)> dist[x]. So the value of dist[x] would not have been updated even if y was considered as a path to x, thus we conclude that it makes sense to only consider neighbors of y which are still in Q (note comment in line16)

But this thing hinges on our assumption of positive edge length, if length(u,v)<0 then depending on how negative that edge is we might replace the dist[x] after the comparison in line18.

So any dist[x] calculation we make will be incorrect if x is removed before all vertices v - such that x is a neighbour of v with negative edge connecting them - is removed.

Because each of those v vertices is the second last vertex on a potential "better" path from source to x, which is discarded by Dijkstra’s algorithm.

So in the example I gave above, the mistake was because C was removed before B was removed. While that C was a neighbour of B with a negative edge!

Just to clarify, B and C are A's neighbours. B has a single neighbour C and C has no neighbours. length(a,b) is the edge length between the vertices a and b.

Answer 3

Dijkstra 的算法假设路径只能变得“更重”，因此，如果您有一条从 A 到 B 的路径权重为 3，而从 A 到 C 的路径权重为 3，则您无法添加边和通过C从A到B，权重小于3。

这个假设使算法比必须考虑负权重的算法更快。

Answer 4

Dijkstra 算法的正确性：

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

归纳假设：在每一步，我们将假设所有先前的迭代都是正确的。

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

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

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

因此，要使 dijkstra 算法起作用，边权重必须为非负数。

Answer 5

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

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

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

Answer 6

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

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

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

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

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

Answer 7

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

在那种情况下，实际上我已经看到最好使用具有正常队列并且可以处理负边缘的SPFA 算法。

Answer 8

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

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

考虑一下：

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

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

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

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

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

那么，完美的路径是什么？每当算法增加一个BC步骤时，它都会将总权重减少 2。

所以最佳路径是永远循环A (BC) D的BC部分。

由于 Dijkstra 的目标是找到最优路径（而不仅仅是任何路径），根据定义，它不能使用负权重，因为它无法找到最优路径。

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

Answer 9

回想一下，在 Dijkstra 的算法中，一旦一个顶点被标记为“关闭”（并且在开放集之外）——它假设任何源自它的节点都会导致更大的距离，因此，算法找到了到它的最短路径，并将永远不必再次开发这个节点，但在负权重的情况下这并不成立。

Answer 10

在前面的答案之上，为以下简单示例添加几点说明，

1. Dijktra 的算法是贪心的，它首先贪婪地找到顶点C到源顶点A的最小距离 ，并将距离d[C]（从顶点A）分配给边AC的权重。
2. 基本假设是，由于首先选择了C ，因此在图 st w(AV) < w(AC)中没有其他顶点V，否则算法会选择V而不是C。
3. 由于根据上述逻辑，对于与顶点A和C 不同的所有顶点V ， w(AC) <= w(AV)。现在，显然任何其他 从A开始并以C结束的路径P，经过 V，即路径P = A -> V -> ... -> C的长度将更长（> = 2）并且路径P的总成本将是其边缘的总和，即cost(P) >= w(AV) >= w(AC) ，假设P上的所有边缘具有非负权重，因此 C可以是安全地从队列Q中移除，因为在这个假设下， d[C]永远不会变得更小/更放松。
4. 显然，当P上的 some.edge 为负时，上述假设不成立 ，在这种情况下d[C] 可能会进一步减小，但算法无法处理这种情况，因为到那时它已将C从队列Q。