Bellman–Ford 最短路算法

Bellman–Ford 通过反复松弛全部边求单源最短路，允许负边权。若从源点可达某个负环，沿环重复行走可以不断降低路径权值；从该负环还能到达的顶点不存在有限最短距离。其他顶点未必受影响。

按路径边数松弛

初始化源点距离为 0，其余为无穷大。每轮扫描所有边，用 $d[u]+w(u,v)$ 尝试降低 $d[v]$。只从当前可达的顶点松弛，避免把无穷大当作普通数参与运算。

经过 $k$ 轮后，距离估计不大于任何至多含 $k$ 条边的路径长度。原地更新可能在一轮内沿多条边传播，所以不能把第 $k$ 轮的值严格等同于“至多 $k$ 条边的最优值”；若要这个精确动态规划状态，需要上一轮数组的副本。

没有可达负环时，总能从最短游走中去掉非负环，得到至多含 $n-1$ 条边的简单路径。因此 $n-1$ 轮足够。

实现与负环检测

以下代码返回距离数组；若检测到源点可达的负环，返回 None。它不进一步区分哪些顶点受负环影响。

from math import inf

def bellman_ford(n, edges, source):
    dist = [inf] * n
    dist[source] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, weight in edges:
            if dist[u] != inf and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                changed = True
        if not changed:
            break
    for u, v, weight in edges:
        if dist[u] != inf and dist[u] + weight < dist[v]:
            return None
    return dist

如果 $n-1$ 轮后仍可松弛，则存在可达负环。反过来，可达负环上的全部边不可能同时满足 $d[v]\le d[u]+w(u,v)$，否则沿环相加会得到 $0\le$ 负数。因此检测不会漏掉可达负环。

要检测整张图中的负环，可以增加一个向所有顶点连零权边的超级源点，或将全部初始距离置为 0。要标记所有受影响顶点，可从额外一轮仍被松弛的顶点出发沿有向边搜索。

时间复杂度为 $O(nm)$，距离数组占 $O(n)$ 辅助空间，边表另占 $O(m)$。

队列优化：SPFA

只有距离变小的顶点，其出边才可能带来新的改进。SPFA 用队列保存这些待处理顶点，另用 in_queue 标记避免重复入队。

它可能省去大量无效扫描，但最坏时间仍为 $O(nm)$，稀疏图也可能退化。存在可达负环时还需要可靠的负环检测，不能只等待队列自然清空。不能把一次样例中的快速运行当作复杂度保证。