Bellman-Ford
进阶Bellman-Ford 通过反复松弛所有边来逼近最短路，能检测负环。
// 算法讲解
Bellman-Ford
输入节点数、起点和带权边，观察 Bellman-Ford 多轮松弛过程。
待机
速度 中
待机 ⌨1bool bellmanFord(int src, int V, vector<tuple<int,int,int>>& edges, vector<long long>& dist) {
2 dist.assign(V, LLONG_MAX);
3 dist[src] = 0;
4 for (int i = 0; i < V - 1; i++) {
5 bool updated = false;
6 for (auto& [u, v, w] : edges)
7 if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
8 dist[v] = dist[u] + w;
9 updated = true;
10 }
11 if (!updated) break;
12 }
13 for (auto& [u, v, w] : edges)
14 if (dist[u] != LLONG_MAX && dist[u] + w < dist[v])
15 return false;
16 return true;
17}
复杂度分析
时间 O(VE)
空间 O(V)
最优 O(E) 提前终止
最坏 O(VE)
算法讲解
Bellman-Ford 对所有边执行 V-1 轮松弛操作，每轮至少确定一个节点的最短距离。
如果在第 V 轮仍有边可以被松弛，说明图中存在负权环。
时间复杂度 O(VE)，比 Dijkstra 慢，但能处理负权边和检测负环。
它常用于带有负权边的最短路问题和差分约束系统的求解。