如何修复处理负值时会生成负环的Floyd最短路径算法？

原代码的问题 #

原代码在每次迭代中强制将dist[i][i]设为0，这会掩盖负环的存在——如果某个节点处于负环中，理论上它到自身的最短路径可以通过绕负环无限缩短（变为负数），但强制重置为0会让算法无法捕捉到这个异常，甚至可能导致错误的路径计算结果。

修复方案 #

要正确处理负环，需要做两件核心修改：

1. 仅在初始化阶段设置dist[i][i] = 0，迭代过程中不再强制重置，让算法自然更新节点到自身的距离。
2. 完成核心的三重循环后，添加负环检测逻辑，标记出受负环影响的节点或路径。

修复后的代码 #

def floyd_warshall_with_neg_cycle(n, graph):
    # 初始化距离矩阵
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0  # 仅初始化时设置自身距离为0
    for i in range(n):
        for j in range(n):
            if graph[i][j] != float('inf'):
                dist[i][j] = graph[i][j]
    
    # Floyd核心迭代
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    # 检测负环：检查是否存在节点i，使得i到自身的距离小于0
    has_neg_cycle = False
    neg_cycle_nodes = []
    for i in range(n):
        if dist[i][i] < 0:
            has_neg_cycle = True
            neg_cycle_nodes.append(i)
    
    # 处理受负环影响的路径：如果i能到达负环，或者负环能到达j，那么i到j的路径可以无限缩短
    if has_neg_cycle:
        # 标记所有能到达负环的节点
        reachable_to_cycle = [False] * n
        for i in range(n):
            for node in neg_cycle_nodes:
                if dist[i][node] != float('inf'):
                    reachable_to_cycle[i] = True
        # 标记所有能从负环到达的节点
        reachable_from_cycle = [False] * n
        for node in neg_cycle_nodes:
            for j in range(n):
                if dist[node][j] != float('inf'):
                    reachable_from_cycle[j] = True
        # 对于i能到负环且负环能到j的路径，设为负无穷（表示可无限缩短）
        for i in range(n):
            for j in range(n):
                if reachable_to_cycle[i] and reachable_from_cycle[j]:
                    dist[i][j] = -float('inf')
    
    return dist, has_neg_cycle, neg_cycle_nodes

代码说明 #

• 初始化阶段：仅在最开始设置节点到自身的距离为0，后续迭代中允许这个值被更新（如果存在负环，会变成负数）。
• 核心迭代：添加了对dist[i][k]和dist[k][j]是否为无穷的判断，避免无效的加法运算。
• 负环检测：通过检查dist[i][i] < 0来判断节点i是否处于负环中。
• 负环影响处理：标记所有能到达负环、以及能从负环到达的节点，将这些节点之间的路径设为负无穷，表示路径长度可以无限缩短（不存在最短路径）。

内容的提问来源于stack exchange，提问作者Алла Ноженко