Bellman-Ford 算法

Bellman-Ford 算法在一般带权图上求单源最短路，允许边权为负（仍要求不存在从 可达的负圈，否则最短路无下界）。算法通过多轮松弛逐步缩短距离估计，并能检测负圈。

---

1. 问题与记号

• 图 ，边权 可为任意实数（实现中常约定无自环或单独处理）。
• 源点 。
• 若存在从 可达的负权回路且该回路上最短路被不断绕圈压低，则问题无有限最优解；算法应报告“负圈”。

---

2. 算法描述

核心：对每条边做松弛 ：若 ，则 。

输入: G, w, s
初始化: dist[s] ← 0；其余 dist ← +∞

重复 |V|-1 次:
    对每条边 (u,v) ∈ E:
        relax(u,v)

再对每条边 (u,v) 执行一次 relax:
    若仍存在 dist[v] 可被更新，则存在从 s 可达的负圈，报告并结束
否则返回 dist

• 迭代轮数为 的原因：任意最短路若存在，在无正环可省的简洁形式下最多经过 条边。
• 时间复杂度 ，稠密图上为 量级。

---

3. 负圈检测

第 轮若某条边仍可松弛，说明沿某条路径还能无限降低距离，等价于存在从 可达的负权回路（即沿该回路可无限绕圈压低总路长）。此时应输出负圈存在，而非有限最短路。

---

4. 与 Dijkstra 的对比

项目	Dijkstra	Bellman-Ford
边权	非负	可含负权
负圈	不涉及	可检测
典型复杂度	$O((	V
适用	非负权单源	一般单源、差分约束等

---

5. 应用简述

• 差分约束系统可规约为最短路或判负圈。
• 作为 Johnson 算法中求势函数、消去重权再跑 Dijkstra 的子过程。
• 边数较少、需负权或负圈判定时常用。

---

备忘

（可在此补：SPFA、队列优化、随机图上的实际表现等。）