Bellman-Ford 的负循环

Question

在具有 V 个节点和 E 条边的有向图中，Bellman-Ford 算法将每个顶点（或者更确切地说，从每个顶点发出的边）松弛 (V - 1) 次。这是因为从源到任何其他节点的最短路径最多包含 (V - 1) 条边。在第V次迭代中，如果一条边可以松弛，说明存在负循环。

现在，我需要通过这个负循环找到其他节点"ruined"。也就是说，一些不在负循环上的节点现在与源的距离为负无穷大，因为从源到位于负循环中的节点的路径上有一个或多个节点。

完成此操作的一种方法是运行 Bellman-Ford 并记下负循环上的节点。然后，从这些节点中运行DFS/BFS标记其他节点。

但是，为什么我们不能运行 Bellman-Ford 2 * (V - 1) 次而不求助于 DFS/BFS 来检测此类节点？如果我的理解是正确的，那么将所有顶点放松 2 * (V - 1) 次应该允许负循环 "propagate" 它们的值到所有其他连接的节点。

补充说明：我在解决这个在线问题时遇到了这种情况：https://open.kattis.com/problems/shortestpath3

我使用的Java代码（以及此处未显示的BFS/DFS）如下：

  // Relax all vertices n - 1 times.
  // And relax one more time to find negative cycles
  for (int vv = 1; vv <= n; vv++) {
    // Relax each vertex
    for (int v = 0; v < n; v++) {
      // For each edge
      if (distTo[v] != (int) 1e9) {
        for (int i = 0; i < adjList[v].size(); i++) {
          int dest = adjList[v].get(i).fst;
          int wt = adjList[v].get(i).snd;

          if (distTo[v] + wt < distTo[dest]) {
            distTo[dest] = distTo[v] + wt;

            if (vv == n) {
              isInfinite[v] = true;
              isInfinite[dest] = true;
            }
          }
        }
      }
    }
  }

Answer 1

在经典情况下，所有节点 "on" 负长度循环与源的距离任意小。因此，在第 v-1 次之后的每次迭代中，从源到此类节点的路径都会变小。该任务要求您对所有此类节点 return -infinity。

您可以使用 Bellman-Ford 算法的修改版本将所有此类节点的距离标记为 -infinity 和运行它 v-1 次以使 -infinity 传播到连接到的所有其他节点周期。但是与循环中节点的运行 DFS 或 BFS 相比，这需要很多额外的时间。

Answer 2

考虑具有 N=4, M=5 的图表：

A -> B weight 1000
A -> C weight 1000
C -> D weight -1
D -> C weight -1
D -> B weight 1000

设 A 为源，B 为目的地。

现在显然有一个负循环(C <-> D)。但是无论我们运行算法N次还是2N次甚至3N次，从A到B的最短路径还是1000。由于负循环每次使用都只是减少了一点距离，所以不会像我们预期的那样传播到其他节点。

一种解决方案是，一旦确定了影响节点的循环，就将距离标记为负无穷大。这样，通过其他节点的其他最短路径的负循环 "takes precendence"。

此致，
一位在这个问题上花了很多时间的编码员。

Bellman-Ford 的负循环

Negative Cycles in Bellman-Ford

algorithm

graph-theory

shortest-path

bellman-ford