找到负循环却得到错误答案

Question

我一直致力于在 Python 中实现 Bellman-Ford 算法，以检测上面链接的问题的负循环。然而，我遇到了障碍。尽管我付出了努力，但我还是遇到了针对问题的错误答案和频繁的超出时间限制 (TLE) 错误。

这是我编写的Python代码：

def bellman_ford(n, edges):
    dist = [float('inf')] * (n + 1)
    dist[1] = 0
    prev = [-1] * (n + 1)
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and  dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    for u, v, w in edges:
        if dist[u]!=float('inf') and dist[u] + w < dist[v]:
            cycle = [v]
            prev[v] = u
            while u != v:
                cycle.append(u)
                u = prev[u]
            cycle.append(v)
            return True, cycle[::-1]
    return False, None
n, e = map(int, input().split())
edges = []
for _ in range(e):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

chk, cycle = bellman_ford(n, edges)
if chk == True:
    print("YES")
    print(*cycle)
else:
    print("NO")

我已经进行了多次试运行，但我无法查明我的实施中的确切缺陷。任何有助于确定我哪里出了问题的帮助将不胜感激。

提前感谢您的帮助！

Answer 1

贝尔曼-福特算法找到从一个选定节点（在您的情况下为节点 1）到所有节点的最短距离。该算法将找到一个负循环仅当可以从节点 1 到达该循环。例如，如果以下是您的输入图：

...那么节点 2 和 3 之间的负循环将不会被检测到，因为它们节点的距离永远不会小于无穷大。

一个务实的解决方案是执行以下操作：

• 检查是否没有发现环路，是否存在距离无穷大的节点。虽然是这样：

  • 从图中删除接收有限距离的所有节点及其连接的边。

  • 在剩余图上重复该算法，从其中一个节点开始（显然，但它可能没有索引 1，具体取决于您执行上一步的方式）。