在具有V节点和E边的有向图中,Bellman-Ford算法放松每个顶点(或者更确切地说,每个顶点的边缘)(V-1)次 . 这是因为从源到任何其他节点的最短路径最多包含(V-1)个边缘 . 在第V次迭代中,如果边缘可以放松,则表明存在负循环 .
现在,我需要通过这个负循环找到其他节点“毁了” . 也就是说,由于从源到节点的路径上的一个或多个节点位于负循环中,所以不在负循环中的一些节点现在具有与源无穷远的距离 .
实现这一目标的一种方法是运行Bellman-Ford并注意负循环上的节点 . 然后,从这些节点运行DFS / BFS以标记其他节点 .
但是,为什么我们不能在不使用DFS / BFS的情况下运行Bellman-Ford 2 *(V-1)次来检测这样的节点?如果我的理解是正确的,放松所有顶点2 *(V - 1)次应该允许负循环将它们的值“传播”到所有其他连接的节点 .
Additional Details: 我在解决这个在线问题时遇到了这种情况: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;
}
}
}
}
}
}
1 回答
在经典情况下,所有在“负”长度周期“上”的节点与源具有任意小的距离 . 因此,在v-1之后的每次迭代中,从源到这样的节点的路径变得更小 . 该任务要求您为所有此类节点返回-infinity .
您可以使用Bellman-Ford算法的修改版本将所有此类节点的距离标记为-infinity并将其运行v-1次以使-infinity传播到连接到该循环的所有其他节点 . 但是,与仅从循环中的节点运行DFS或BFS相比,这需要大量的额外时间 .