Bellman-Ford 算法
最后更新
Bellman-Ford 算法求出从源节点到其他每个节点的最短路径。和 Dijkstra 算法不同，即使有些边的权重为负，它也能正常工作。它靠暴力松弛来实现：反复扫描每一条边，如果经过这条边能得到更短的距离，就更新目标节点的距离。点击上方的“播放”，观察暂定距离如何一轮一轮地下降。
对所有边执行 V - 1 轮之后，每条最短路径（最多包含 V - 1 条边）都已找到。因此它的复杂度是 O(V · E)，比 Dijkstra 慢，但它能处理负权边，还能检测负权回路（如果第 V 轮仍能松弛某条边，就不存在最短路径）。
时间和空间复杂度
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间 | O(V · E) | 对全部 E 条边执行 V − 1 轮 |
| 空间 | O(V) | 每个节点存一个距离 |
| 负权边 | 支持 | 这是它相对 Dijkstra 的主要优势 |
| 负权回路 | 可检测 | 第 V 轮仍有松弛就说明存在负权回路 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 把源节点的距离设为 0，其他节点都设为无穷大。 |
| 2 | 把下一步重复 V − 1 次。 |
| 3 | 对每条边 (u → v, w)，检查是否 dist[u] + w < dist[v]。 |
| 4 | 如果是，就松弛它：令 dist[v] = dist[u] + w。 |
| 5 | 如果一整轮都没有变化，就提前结束。 |
示例演算
源节点为 S，共 4 个节点 S, A, B, C，边为 S→A (4)、S→B (5)、A→C (3)、B→A (-3)，按这个顺序松弛。初始距离为 S=0，其余都是 ∞：
| 轮次 | 距离 [S, A, B, C] | 操作 |
|---|---|---|
| 初始化 | [0, ∞, ∞, ∞] | 源节点距离为 0，其余为无穷大。 |
| 1 | [0, 2, 5, 7] | 松弛 S→A 得到 4，S→B 得到 5，A→C 得到 7，然后 B→A 把 A 降到 5 + (-3) = 2。 |
| 2 | [0, 2, 5, 5] | A→C 现在把 C 改进为 2 + 3 = 5，其他边都没有松弛。 |
| 3 | [0, 2, 5, 5] | 没有边被松弛，距离已是最终结果：经 S→B→A 到 A 的代价为 2。 |
什么时候使用 Bellman-Ford
| 适合使用的情况 | 不适合使用的情况 |
|---|---|
| 边的权重可能为负。 | 所有权重都非负（Dijkstra 更快）。 |
| 必须检测负权回路。 | 图非常大且稠密，O(V · E) 太慢。 |
| 图较小或较稀疏。 | 在大图上只需要查询一个源点到一个终点。 |
| 需要一个简单、易实现的基准算法。 | 权重非负，并且对延迟敏感。 |
Bellman-Ford Algorithm 代码
简洁、可运行的 Bellman-Ford Algorithm 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Bellman-Ford Algorithm 的 Python 代码
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")Bellman-Ford Algorithm 的 JavaScript 代码
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Bellman-Ford Algorithm 的 Java 代码
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}Bellman-Ford Algorithm 的 C++ 代码
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}Bellman-Ford Algorithm 的 C 代码
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}Bellman-Ford 常见问题
Bellman-Ford 算法的时间复杂度是多少？
Bellman-Ford 的运行时间为
O(V · E)：它执行 V - 1 轮，每轮松弛全部 E 条边。这比 Dijkstra 的 O((V + E) log V) 慢，是支持负权边要付出的代价。什么时候该用 Bellman-Ford 而不是 Dijkstra？
当图中可能有负权边，或者需要检测负权回路时，用 Bellman-Ford。Dijkstra 更快，但只在权重非负时才正确。一个常见的实际用途是检测货币兑换中的套利机会，这里负权回路至关重要。
Bellman-Ford 如何检测负权回路？
如果不存在负权回路，经过
V - 1 轮松弛后，所有最短路径都已确定。如果再执行一轮仍能松弛某条边，说明可以到达一个负权回路，最短路径就没有定义（你可以无限绕圈来降低代价）。Bellman-Ford 和 Floyd-Warshall 有什么区别？
Bellman-Ford 以
O(V · E) 计算单源最短路径，而 Floyd-Warshall 以 O(V³) 计算所有点对之间的最短路径。在稠密图上，从每个源点各运行一次 Bellman-Ford 的代价是 O(V² · E)，所以需要所有点对时，Floyd-Warshall 通常是更好的选择。两者都能处理负权边，也都能发现负权回路。为什么 Bellman-Ford 恰好需要 V - 1 轮？
在没有负权回路的图中，任何最短路径最多使用
V - 1 条边，因为访问超过 V 个节点的路径必然会重复经过某个节点。每一轮都保证每条最短路径上至少再有一条边被正确松弛，所以 V - 1 轮足以确定全部最短路径。一个常见的误解是轮数越多答案越好，但除非存在负权回路，多出来的轮次不会带来任何改进。Bellman-Ford 可以提前结束吗？
可以。如果对所有边的一整轮扫描都没有松弛任何边，说明每个距离都已是最优，你可以在
V - 1 轮之前就停止。这种提前退出的优化在收敛很快的图上通常能大幅提速，但最坏情况下的复杂度仍是 O(V · E)。相关资源
更多可视化
