Bellman-Ford算法负权环检测原理及示例解析

首先得明确Bellman-Ford算法的一个基础前提：对于一个不存在源点可达负权环的n节点图，任意节点到源点的最短路径最多包含n-1条边。原因很简单：最短路径不可能重复走同一个节点——如果路径里套了环，绕环走一圈要么加正权（走了反而更长，纯冤枉路），要么零权（走不走没区别），把环去掉之后路径只会更短或者等长，边数肯定超不过n-1。
算法前n-1轮的全边松弛操作，就是逐轮算出「最多走k条边」时各节点的最短距离，k从1涨到n-1。如果没有负环，n-1轮跑完之后所有节点的最短距离就已经收敛到真实值了，不可能再找到更短的路径。

v.d > u.d + w(u,v)的检测原理 #

伪代码里n-1轮松弛结束后，会再遍历所有边做一次判断，只要存在任意一条边(u,v)满足v.d > u.d + w(u,v)，就直接判定图里存在源点可达的负权环，返回False。
这个判断的逻辑非常直白：如果n-1轮之后还能通过边(u,v)把v的距离改得更小，就说明存在一条走了n条边到v的路径，比之前所有走≤n-1条边的路径都短。而n个节点的路径里必然包含至少一个环，这个环的总权重一定是负数——毕竟绕这个环走一圈，总路径长度反而变小了，你要是愿意多绕个几圈，路径总长度能无限降低，根本不存在确定的最短路径，这就是负权环的典型特征。

具体示例演示 #

拿一个3节点的简单带负环的图举例：

• 源点为s，共3个节点：s、a、b
• 边列表：
  • s→a（权重5）
  • a→b（权重-1）
  • b→a（权重-3）
    其中a和b构成的环总权重是-1 + (-3) = -4，属于负权环。

我们一步步跑算法流程：

1. 初始化距离：s.d=0，a.d=+∞，b.d=+∞
2. 跑满n-1=2轮全边松弛：
   • 第1轮松弛（对应最多走1条边的路径）：
     • 走s→a：a.d更新为0+5=5
     • 走a→b：b.d更新为5+(-1)=4
     • 走b→a：a.d更新为4+(-3)=1
       第一轮结束后距离：s=0，a=1，b=4
   • 第2轮松弛（对应最多走2条边的路径）：
     • s→a：当前a.d=1 < 0+5=5，不更新
     • a→b：b.d更新为1+(-1)=0
     • b→a：a.d更新为0+(-3)=-3
       第二轮（也就是n-1轮）结束后距离：s=0，a=-3，b=0
3. 进入负环检测环节，遍历所有边做判断：
   • s→a：当前a.d=-3 < 0+5=5，不触发松弛
   • a→b：当前b.d=0，而u.d + w(u,v) = -3 + (-1) = -4，明显满足v.d > u.d + w(u,v)（0 > -4），还能继续松弛
     这时候直接判定存在可达负权环。

你可以顺着算下去：哪怕你多跑几轮松弛，a和b的距离会越来越小——每绕a→b→a的环走一圈，总距离就减4，根本没有下限，自然不存在合法的最短路径，这就是这个判断条件能抓到负环的本质原因。
要注意的是，不一定只有负环上的节点会触发这个条件：只要是负环能到达的节点，n轮之后都能被继续松弛，毕竟你可以多绕负环几圈凑出更短的到该节点的路径。

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