在具有V节点和E边的有向图中，Bellman-Ford算法将每个顶点(或者更确切地说，每个顶点的边(放宽(V - 1(次。这是因为从源到任何其他节点的最短路径最多包含 (V - 1( 边。在第 V 迭代中，如果边可以松弛，则表示存在负循环。
现在，我需要找到被这个负循环"毁掉"的其他节点。也就是说，一些不在负循环上的节点现在与源的距离为负无穷大，因为从源到节点的路径上的一个或多个节点位于负循环中。
实现此目的的一种方法是运行Bellman-Ford并记下负循环中的节点。然后，从这些节点运行 DFS/BFS 以标记其他节点。
但是，为什么我们不能在不诉诸DFS/BFS的情况下运行Bellman-Ford 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;
}
}
}
}
}
}
考虑一个带有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。由于负循环每次使用时只会减少少量的距离，因此它不会像我们预期的那样传播到其他节点。
一种解决方案是在确定影响节点的周期后将距离标记为负无穷大。这样，负循环"优先于"通过其他节点的其他最短路径。
你的真诚，
一个在这个问题上花了很多时间的程序员同事。
在经典情况下，负长度循环上的所有节点到源的距离都很小。 因此，在 v-1 之后的每次迭代中，从源节点到此类节点的路径都会变小。 该任务要求您为所有此类节点返回 -无穷大。
您可以使用 Bellman-Ford 算法的修改版本将所有此类节点的距离标记为 -无穷大，并将其运行 v-1 次以使 -infinity 传播到连接到循环的所有其他节点。但是，与仅从周期中的节点运行DFS或BFS相比，这需要大量额外的时间。