Bellman-Ford负环检测算法：初始化dist为float('inf')为何失败？

你遇到的问题核心是不可达负环的检测差异，以下是具体原因：

问题代码 #

def negative_cycle(n, graph):
    # dist = [float('inf')] * (n+1)  (This code fails)
    dist = [1001] * (n+1)          # (this code doesn't)
    dist[1] = 0
    for i in range(n):
        for st, end, cost in graph:
            print(dist)
            if dist[end] > dist[st] + cost:
                dist[end] = dist[st] + cost
                if i == n - 1:
                    return 1
    return 0


if __name__ == '__main__':
    n_vertices, n_edges = map(int, input().split())
    edges = []
    for i in range(n_edges):
        a, b, w = map(int, input().split())
        edges.append((a, b, w)) 
    print(negative_cycle(n_vertices, edges))

原因分析 #

• float('inf')初始化的局限性：
  这种初始化下，只有起点1的dist为0，其他节点都是无穷大。如果测试用例中存在和起点1完全不连通的负环，环上所有节点的dist会一直保持无穷大。由于无穷大加上任何负权值仍然是无穷大，松弛条件dist[end] > dist[st] + cost永远不成立，代码无法检测到这个负环，导致返回错误结果。
• 1001初始化的特殊性：
  用有限值初始化时，所有节点的初始dist都是1001。即使负环和起点不连通，环上节点的dist在松弛过程中会被不断更新（比如1001加上负权值会小于1001）。当循环到第n轮（i == n-1）时，松弛操作会触发条件，返回存在负环，从而“正确”检测到这个不可达的负环。

补充说明 #

你的代码原本逻辑是检测从起点1可达的负环，这是Bellman-Ford的常规用法之一。如果需要检测全局所有负环（包括不可达的），标准做法是将所有节点的dist初始化为0，或者在完成n-1轮松弛后，额外对所有边做一次松弛，只要有节点的dist能被更新，就说明存在负环。

内容的提问来源于stack exchange，提问作者Ali Alsawad