我们能否修改Dijkstra算法以处理负权重？

Question

我们能否修改Dijkstra算法以处理负权重？

algorithmdijkstradirected-graphsingle-source

7

以下是从维基百科提取的伪代码:

function Dijkstra(Graph, source):
 2      for each vertex v in Graph:                                // Initializations
 3          dist[v] := infinity ;                                  // Unknown distance function from source to v
 4          previous[v] := undefined ;                             // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                                        // Distance from source to source
 7      Q := the set of all nodes in Graph ;                       // All nodes in the graph are unoptimized - thus are in Q
 8      while Q is not empty:                                      // The main loop
 9          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
10          if dist[u] = infinity:
11              break ;                                            // all remaining vertices are inaccessible from source
12          end if ;
13          remove u from Q ;
14          for each neighbor v of u:                              // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:                                  // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19                  decrease-key v in Q;                           // Reorder v in the Queue
20              end if ;
21          end for ;
22      end while ;
23      return dist[] ;
24  end Dijkstra.

现在，在第14行中，我们可以看到仅对Q中尚未删除的邻居u应用松弛操作。但是，如果我们还考虑已从Q中删除的u的邻居，则我认为该算法确实适用于负权重。我没有找到任何与此主张相矛盾的实例。

那么，为什么迪杰斯特拉算法不会以这种方式改变呢？

- Ori Popowski

6个回答

7

Dijkstra能够访问每个节点一次，因为当它选择一个新节点进行访问时，它会选择从根节点开始的路径最短的未访问节点。因此，它可以安全地假设通过另一个未访问节点到达该节点的任何更短路径不存在（因为如果你已知从A到B的最佳路径成本为2，而从A到C的最佳路径成本为3，则不可能找到一条从A到B的更好路径如A>C>B）。

如果您添加负权重，您将突然打破这个假设。

您当然可以使用您提出的修改，但那样您将失去仅访问每个节点一次的好处；因此，与Ford-Bellman等其他算法相比，它会失去性能优势。

- Pyra

4

你基本上有两个选择。

你可以按照你的建议更改算法。如果你有一个没有负循环的有向图，那么这是一个正确的算法，但它可能会非常慢（因为你将多次访问每个节点）。我认为在某些情况下，这个算法的时间复杂度是指数级的。
你可以通过使用势能来改变边的成本。每个顶点都有一些势能h(v)，边u->v的权重将为w(u,v)+h(u)-h(v)。请注意，这不影响给定两个顶点（s，t）之间的最短路径，只是其成本受到h(s)-h(t)的影响。但你需要计算势能。在这里提出了一个好的方法：http://en.wikipedia.org/wiki/Johnson's_algorithm。

- usamec

3

不，按照现有的说法是不可能的。除非你对提供的图形类型进行了严格限制，否则带有负权重的算法就没有意义。

假设有一个包含节点A、B、C和边权AB=-1、BA=0、BC=1的图形。

现在A和C之间不再存在最短路径，而你可以通过在A和B之间来回走一次来找到更短的路径。

当然，算法仍然会运行，但它会给出错误的答案。

- Deestan

具有所述修改的算法永远不会给出错误答案。它只在正确答案存在时给出正确答案（在您的情况下，最短路径问题本身是未定义的）。否则，它将不会终止（可以通过迭代的上限和抛出异常来轻松修复）。 - mastov

2

是的，您的修改在两个假设下可以运行，这两个假设您没有提到，但我想是暗示了的：

1.最短路径必须在您的输入图中实际定义。如果取消非负权重的限制，则至少必须要求没有负权重的循环。 2.第19行中的“Q中的decrease-key v”操作对于不在Q中的节点v并没有实际意义。但是，当然，您可以使用新值将其重新添加到Q中。

然而，您会失去Dijkstra算法的一个重要特性：其良好的最坏情况渐近性能。现成的Dijkstra保证良好的性能，因为它最多只访问每个节点和每条边一次。包括您的更改后，已经删除的节点可能会被重新添加到优先级队列中，并且可能需要反复访问图的大部分。在最坏的情况下，您必须执行与Bellman-Ford算法相同数量的松弛操作，但您还有优先级队列的额外开销。这使得您的最坏情况性能比Bellman-Ford更差，因此Bellman-Ford更适用于具有负边的图。

这并不意味着您修改后的Dijkstra无用。如果您具有非常少的负边和/或这些负边与其余图通过昂贵的路径分离，则它可以比Bellman-Ford表现更好。但是请准备好相当糟糕的最坏情况性能。

- mastov

1

在修改版的Dijkstra算法中，仅仅放松已经访问过的节点是不够的（并且在包含负边的图中会给出错误的答案）。此外，您需要将任何被放松的边加入到容器中（例如优先队列或普通队列）。因此，您可以从第19行开始修改代码：

if v is in priority queue
    then decrease-key(v)
else
    add v into priority queue

在这种情况下，你的算法可以工作。此外，对于修改版的Dijkstra算法，在正加权图中效率不会降低。这很容易证明，因为这本质上是一种贪心算法。

然而，对于包含负边的图，新算法在理论分析方面可能会变得缓慢，但在实践中它会表现良好。

实际上，你可以看一下一个名为SPFA（Shortest Path Faster Algorithm）的算法，该算法由中国的段定凡（1994年）发布。许多OIer（信息奥林匹克竞赛选手）知道这个算法，因为它有时可能会击败Dijkstra算法。

- Cherish

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shahbaz · Accepted Answer

你可以通过确保不重复遍历任何节点或边来使Dijkstra算法适用于负值。这里，通过“适用”，我指的是终止。然而，结果可能不是最优的。

Dijkstra的算法具有贪心的意义。想象一下以下图形：

A --- 1 --- B
|           |
3          -4
|           |
C -- -1 --- D

如果我们想从A到B，最佳路径是A-C-D-B，但Dijkstra算法找到的是A-B。你不能让Dijkstra算法“预测未来”，因为它是一种贪心算法。所谓“预测未来”，是指知道以后路径的成本可能会降低。请注意，这意味着如果将您的修改应用于立即在看到目标时终止的Dijkstra算法版本，则您的修改将不正确地工作。在您发布的版本中，您的修改有效，除非处理负边的更有效方法（请参见注释）。另外，对于带有负值的无向图或带有负循环的有向图，最短路径甚至没有意义！