图(3)：含负边的最短路径算法

本文为算法课程的知识点复习，主要复习内容为含负边的最短路径算法——Bellman-Ford算法。

Bellman-Ford算法

算法特点

• 允许处理负权边
• 通过多轮松弛操作逐步逼近最优解
• 可检测图中是否存在负权环

算法步骤

1. 初始化：源点距离设为0，其他顶点距离设为无穷大

2. 松弛操作：对每条边$(u, v)$，$dist[v] = \min(dist[v], dist[u] + d(u, v))$

3. 迭代过程：执行 $V-1$ 轮松弛操作

4. 负权环检测：额外执行第$V$轮松弛，若仍有距离更新则存在负权环

正确性证明

• 引理1：第 $k$ 轮松弛后，$dist[v]$ 是最多含 $k$ 条边的最短距离。

  • 可用数学归纳法证明

• 引理2：无负权环时，$V-1$ 轮后必达稳定状态。

时间复杂度

• 时间复杂度为 $\bm{O(|V| \cdot |E|)}$

Dijkstra 算法与 Bellman-Ford 算法对比

特征	Dijkstra算法	Bellman-Ford算法
适用范围	仅非负权图	任意权图（含负权）
时间复杂度	$O(|E| + |V| \log |V|)$	$O(|V| \cdot |E|)$
空间复杂度	$O(|V|)$	$O(|V|)$
处理负权边	不可用	支持
检测负权环	无此功能	支持