Bellman–Ford 算法

同步版本第 $i$ 轮回答“最多走 $i$ 条弧能有多便宜”。原地扫描保留这条进度保证，却可能沿当前边序一次跨过多步；所以轮号是最坏进度下界，不再精确等于已传播的路径长度。只要一条最短路还没有完整传播，每一整轮至少会把正确前缀向前推进一条弧。

与Dijkstra 算法理路Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。不同，Bellman–Ford 从不永久结算某个顶点。负边可能让后来到达的长前缀反而更便宜，反复扫描正是允许这种信息回传的机制。经过足够多轮仍能下降时，简单路的 $n-1$ 条弧上限已耗尽，额外改进只能借助重复顶点；其中必有负权圈。

设边 $s\to a$ 权 $2$、$a\to b$ 权 $-5$、$s\to b$ 权 $4$。若一轮按 $s\to a,a\to b,s\to b$ 扫描，第一轮就得到 $(d[a],d[b])=(2,-3)$；若先扫 $a\to b$，第一轮结束为 $(2,4)$，第二轮才把 $b$ 降到 $-3$。边序影响到达稳定值的轮数，不影响 $n-1$ 轮后的答案，因此“整轮无更新即提前停止”是安全的。

负边与负圈承担不同语义：前者只要求标签允许回改，后者让一部分距离根本没有有限最小值。想恢复负圈，可在原地版第 $n$ 轮记录任一被松弛顶点 $x$，沿前驱回退 $n$ 次以进入前驱圈，再走到顶点重复为止；输出相应的前驱弧编号，并反转回溯顺序，便得到可逐弧核验的有向负圈。若要标记所有距离为 $-\mathrm{\infty }$ 的顶点，应收集第 $n$ 轮仍可改进的顶点，并从它们沿出弧做可达性搜索；只把圈上顶点标负无穷会漏掉圈的后继。

负环检测可以用一个完整的小图看清。设有边

环 $a\to b\to a$ 的总权为 $-2$，且从 $s$ 可达；每绕一圈，$a,b$ 的估计再降 $2$。顶点 $c$ 不在圈上，却可由圈到达，所以 $\delta (s,c)=-\mathrm{\infty }$。另一个与 $s$ 不连通的负圈端点始终为 $+\mathrm{\infty }$，不会触发本次单源检测。平行弧只需逐条松弛；自环若权为负，会在可达时立即成为负圈证书。

Bellman–Ford 还能判断差分约束可行性：不等式 $x_v-x_u\le c$ 对应弧 $u\to v$、权 $c$，负圈恰是矛盾证书。距离向量路由把松弛分散到相邻路由器，但异步消息、失效传播与 count-to-infinity 需要额外协议分析，不能直接沿用集中式 $O(n+nm)$ 界。

距离向量路由理路距离向量路由与失效传播Distance-vector routing · 距离向量协议 · Count to infinity让相邻路由器交换距离估计，复算稳定路径、坏消息导致的计数到无穷，以及毒性逆转能排除二节点互指却仍允许三节点循环的边界。把这项额外义务具体化：先从无穷初始化复算同步两轮，再断开直连出口，观察A与B把彼此旧通告更新成3、4、5。毒性逆转排除已经交付反向无穷通告的两节点互指，却仍须面对三节点依赖环；动态协议的缓存和消息事件不能从一次集中式扫描轨迹中省掉。

Johnson 全源最短路理路Johnson 全源最短路算法Johnson's algorithm · Johnson all-pairs shortest paths以 Bellman–Ford 势函数把无负环图重赋为非负边权，再重复 Dijkstra 求稀疏图全源最短路。用 Bellman–Ford 生成可行势并检测全图负圈，再在非负重赋权图上逐源运行 Dijkstra。Floyd–Warshall理路Floyd–Warshall 算法Floyd–Warshall algorithm以允许的中间顶点集合为阶段计算全部顶点对最短路。则按允许的中间顶点做稠密矩阵动态规划；二者的输入表示和复杂度优势区间不同。

Karp 最小平均环算法理路最小平均费用环Minimum mean cycle · Minimum cycle mean · Karp minimum mean cycle algorithm用恰好边数的动态规划求最小环均值，再以移权势与紧弧环同时证明下界和可达到性。也按弧数分层，却要求“恰好 k 条弧”，不能保留上一行值后仍套用均值差商公式。求出均值后，它移权并调用全点零源的本算法产生势，再在紧弧图恢复真正达到均值的环。