Bellman-Ford 最短路

图算法 · 单源最短路径（可含负权）

当最短路遇上负权边

Dijkstra 求单源最短路又快又好，但有个硬前提：边权非负。一旦图里有负权边，它的「贪心取当前最近点、一锤定音」就会出错——一个点可能之后被一条含负权的更短路径再次刷新。Bellman-Ford 正是为此而生。

Bellman-Ford 怎么做

它不挑点，也不贪心，而是反复「松弛」所有边：对每条边 u→v(w)，如果「先到 u 再走这条边」比「当前到 v」更短，就更新 dist[v]。把所有边都这样扫一遍算一轮，一共做 V−1 轮（V 是点数）。

为什么是 V−1 轮？因为任何最短路最多经过 V−1 条边；每做一轮，至少能把「再多一条边可达」的最短距离敲定，V−1 轮后全部收敛。下面固定一张 5 个点的含负权有向图（源 A，含 B→C=−3、D→E=−2）。点「下一步」逐步看每轮怎么扫边：当前边黄色高亮，能松弛就让终点的距离徽标下降——特别留意 D、E 的距离要经过好几轮才逐步降到最终值（这正是需要 V−1 轮的原因），走到底点亮最短路树（绿边）。右侧代码随每一步同步高亮。

源 A 距离置 0，其余置 ∞

1function bellmanFord(edges: [number, number, number][], n: number, source: number): number[] {
const dist = Array(n).fill(Infinity);
dist[source] = 0;
for (let k = 0; k < n - 1; k++) {
  for (const [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}
return dist;
12}

轮次 k-

总轮数 V−14

当前边-

本轮已更新0

dist[A]0

dist[B]∞

dist[C]∞

dist[D]∞

dist[E]∞

1 / 34

复杂度 O(V·E)——比 Dijkstra 慢，但能吃下负权。它还能顺带检测负环：跑完 V−1 轮后再多跑一轮，若还能松弛任何边，就说明图里有负权环（最短路无下界，无意义）。

Dijkstra vs Bellman-Ford

Dijkstra：贪心取当前最近点、一次定一点，要求边权非负，堆优化后 O((V+E)log V)，快。
Bellman-Ford（本页）：盲扫所有边 V−1 轮，能处理负权、能检测负环，O(V·E)，稳。
有负权用 Bellman-Ford，全正权优先 Dijkstra。多源最短路（任意两点）另有 Floyd。

想复习正权图上的贪心最短路，去看 Dijkstra 最短路——两页正是同一类问题的两种解法。

彩蛋：差分约束——最短路解不等式组

Bellman-Ford 有个漂亮的隐藏技能：解差分约束系统。一组形如 x_v − x_u ≤ w 的不等式（工期先后、事件间隔这类约束都长这样），每条恰好对应一条边 u → v（权 w）——因为最短路的三角不等式 dist[v] ≤ dist[u] + w 与它一模一样。于是：建图跑 Bellman-Ford，dist 数组就是一组可行解；出现负环 = 约束互相矛盾、无解。负权边随手就来，这活非 Bellman-Ford 莫属——「解不等式」与「跑最短路」在此合流。

算法可视化

Bellman-Ford 最短路

当最短路遇上负权边

Bellman-Ford 怎么做

Dijkstra vs Bellman-Ford

彩蛋：差分约束——最短路解不等式组