Bellman-Ford算法无法检测负权环且非源点1时结果异常求助

核心错误：松弛循环次数错误 #

你的代码中，松弛阶段的循环次数用了len(vertices)-1（边数-1），但Bellman-Ford算法要求循环节点数-1次，这是最关键的错误：

• 最长的最短路径最多包含n-1条边（n为节点数），因此只需要循环n-1次就能完成所有可达节点的松弛。
• 你已经计算了num_nodes，但没有在循环中使用，导致当边数和节点数不一致时，要么松弛不充分，要么做无用功。

负权环检测问题 #

1. 标准逻辑是正确的：你写的负权环检测逻辑distance[source] != float("Inf") and distance[source] + cost < distance[dest]完全符合算法定义，问题出在之前的松弛循环次数错误，导致松弛不彻底，无法触发检测条件。
2. 检测范围限制：Bellman-Ford只能检测源点可达的负权环。如果负权环不在源点的可达路径上，那些节点的distance始终为inf，自然无法触发检测。
3. 错误修改的巧合：你把条件改成< distance[source]能“检测”到，只是特定测试用例下的巧合，完全不符合算法逻辑，不能作为正确实现。

源点非1时的输出问题 #

你给出的测试图中，源点3没有任何出边，因此确实无法到达节点1和2，输出inf是正确结果。如果期望能到达这些节点，需要在图中添加对应的路径（比如(3,2,1)、(2,1,1)这类边）。

修正后的代码 #

def bellman_ford(graph, source):
    # 提取所有节点并统计数量
    vertices = [node for edge in graph for node in edge[:2]]
    uniquevalues = list(set(vertices))
    num_nodes = len(uniquevalues)

    distance = {i: float("Inf") for i in uniquevalues}
    distance[source] = 0
 
    # 松弛阶段：循环节点数-1次
    for _ in range(num_nodes - 1):
        updated = False
        for u, v, cost in graph:
            if distance[u] != float("Inf") and distance[u] + cost < distance[v]:
                distance[v] = distance[u] + cost
                updated = True
        # 如果本轮没有更新，提前终止循环
        if not updated:
            break

    # 检测负权环
    for u, v, cost in graph:
        if distance[u] != float("Inf") and distance[u] + cost < distance[v]:
            print("Graph contains a negative-weight cycle reachable from source")
            return None
    return distance

# 测试带负权环的图
graph_with_cycle = [
    (1, 2, -2),
    (2, 3, -2),
    (3, 2, -1),  # 新增这条边，形成2→3→2的负权环
    (1, 3, 1),
]

# 源点1，能检测到负权环
shortest_path = bellman_ford(graph_with_cycle, 1)
print(shortest_path)

# 源点3，能检测到负权环（因为源点在环内）
shortest_path = bellman_ford(graph_with_cycle, 3)
print(shortest_path)

# 测试原图，源点3的情况
original_graph = [
    (1, 2, -2),
    (1, 3, 1),
    (2, 3, -2),
]
shortest_path = bellman_ford(original_graph, 3)
print(shortest_path)

测试结果说明 #

1. 带负权环的图，源点1或3时，算法会输出负权环提示并返回None。
2. 原图源点3时，输出{1: inf, 2: inf, 3: 0}是正确的，因为没有从3出发到1、2的路径。

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