Bellman-Ford的负循环

Question

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

现在，我需要找到被这个负循环“毁掉”的其他节点。也就是说，一些不在负循环上的节点由于路径上的一个或多个节点从源到处于负循环的节点之间现在有一个负无穷远的距离。

实现这一目标的一种方法是运行Bellman，并注意负周期上的节点。然后，从这些节点运行DFS/BFS来标记其他节点。

然而，为什么我们不能在不诉诸DFS/BFS的情况下运行Bellman 2*(V-1)来检测这些节点呢？如果我的理解是正确的，放松所有顶点2*(V-1)次数应该允许负循环将其值“传播”到所有其他连接节点。

其他详细信息：--我在解决这个在线问题时遇到了这种情况：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

考虑一个带有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。由于负循环只在每次使用时将距离减少一小部分，所以它并不像我们所期望的那样与其他节点相匹配。

一种解决方案是，一旦确定了影响节点的周期，就将距离标记为负无穷大。这样，负循环“取得优先”的其他最短路径通过其他节点。

你诚心的，

一个在这个问题上花了很多时间的程序员。

Answer 2

在经典情况下，所有“在”负长度周期上的节点都有一个与源的任意小距离。因此，在v-1之后的每一次迭代中，从源到这样的节点的路径都会变小。该任务要求您返回所有此类节点的-infinity。

您可以使用Bellman算法的修改版本来标记所有节点(如-infinity )的距离，并运行v-1次，以便将-infinity传播到连接到循环的所有其他节点。但是与循环中的节点运行DFS或BFS相比，这需要大量额外的时间。