使用Dijkstra算法负权重 [英] Negative weights using Dijkstra's Algorithm

问题描述

我试图理解为什么Dijkstra算法不会负权重的工作。阅读最短路径的一个例子，我想弄清楚以下情形：

I am trying to understand why Dijkstra's algorithm will not work with negative weights. Reading an example on Shortest Paths, I am trying to figure out the following scenario:

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

从网站：

假设边缘都被引导从左至右，如果我们开始   用A，Dijkstra算法会选择边（A，X）最小化   D（A，A）+长度（边缘），即（A，B）。然后，它设置D（A，B）= 2，并选择   另一边（Y，C）减少D（A，Y）+ D（Y，C）;唯一的选择是（A，C）   它集D（A，C）= 3。但它从来没有发现的最短路径从A到   B，通过C，总长度为1。

Assuming the edges are all directed from left to right, If we start with A, Dijkstra's algorithm will choose the edge (A,x) minimizing d(A,A)+length(edge), namely (A,B). It then sets d(A,B)=2 and chooses another edge (y,C) minimizing d(A,y)+d(y,C); the only choice is (A,C) and it sets d(A,C)=3. But it never finds the shortest path from A to B, via C, with total length 1.

我不明白为什么使用Dijkstra算法，D [B]下面的实施将不会被更新，以 1 （当算法达到顶点C，它会运行一个基于B放松，看到D [B]等于 2 ，因此更新其值设置为 1 ）。

I can not understand why using the following implementation of Dijkstra, d[B] will not be updated to 1 (When the algorithm reaches vertex C, it will run a relax on B, see that the d[B] equals to 2, and therefore update its value to 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

谢谢

梅厄

推荐答案

已建议将确实发现在该曲线图中的最短路径算法，但不是所有的一般的图表。例如，考虑一下图：

The algorithm you have suggested will indeed find the shortest path in this graph, but not all graphs in general. For example, consider this graph:

假设边缘被引导从左至右在例如

Assume the edges are directed from left to right as in your example,

您算法的工作方式如下：

Your algorithm will work as follows:

1. 首先，将 D（A）到零和其他距离为无限。
2. 您然后展开了节点 A ，设置 D（B）到 1 ， D（C）到零和 D（D ）到 99 。
3. 接下来，展开了 C ，没有净变化。
4. 您然后展开了 B ，它没有任何效果。
5. 最后，您展开 D ，从而改变 D（B）到 -201 。

1. First, you set d(A) to zero and the other distances to infinity.
2. You then expand out node A, setting d(B) to 1, d(C) to zero, and d(D) to 99.
3. Next, you expand out C, with no net changes.
4. You then expand out B, which has no effect.
5. Finally, you expand D, which changes d(B) to -201.

请注意，在本月底，虽然， D（C）还是 0 ，<强>即使最短路径 C 的长度 -200 。您的算法，因此无法精确计算距离的情况。而且，即使你要存回球说，如何从每个节点的起始节点 A ，你最终走错路回程从<$ C $得到ç> C 到 A 。

Notice that at the end of this, though, that d(C) is still 0, even though the shortest path to C has length -200. Your algorithm thus fails to accurately compute distances in some cases. Moreover, even if you were to store back pointers saying how to get from each node to the start node A, you'd end taking the wrong path back from C to A.

这篇关于使用Dijkstra算法负权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！