最短路径--Bellman-Ford算法详解

keyipatience:个人主页作者简介C/C后端开发学习者专栏传送门《c》《linux》《c高阶数据结构》《c数据结构与算法》⭐️patience is key in lifeBellman-Ford算法Dijkstra仅支持正权图单源最短路朴素版复杂度 O (N²)效率高不能处理负权边无法检测负环。Bellman-Ford优势支持负权边的单源最短路还可以检测源点可达的负权回路。标准邻接表实现时间复杂度 O (N*E)如果用邻接矩阵实现就是咱们写的代码复杂度变成 O (N³)属于暴力松弛效率更差。缺点时间开销通常高于 Dijkstra速度慢。一句话概括Dijkstra 快但怕负权Bellman-Ford 能处理负权、判负环但代价是时间复杂度更高邻接矩阵写法会进一步恶化复杂度到 O (N³)。代码实现CLRS《算法导论》版本直接修改 dist 数组本轮更新的点本轮后面的边可以立刻被用到。 有可能提前就把长路径算出来不需要等到第 n‑1 轮。bool BellmanFord(const V src, vectorW dist, vectorint ppath) { int n _vertexs.size(); int srci GetVertexIndex(src); dist.resize(n, MAX_W);//dist[]的含义目前我们已经探索过的路径里起点 s 到这个点的最短距离 ppath.resize(n, -1); // 初始化ppath数组全部为-1 dist[srci] W();//源点到自己的距离为0; cout 依次选 i-j endl; for (int k 0; k n-1; k) { bool exchange false; for (int i 0; i n; i) { for (int j 0; j n; j) { //srci-uw(u-v)srci-v更新 if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]) { cout _vertexs[i] - _vertexs[j] -_matrix[i][j] endl;; dist[j] dist[i] _matrix[i][j]; ppath[j] i; exchange true; } } } return true; if (exchange false)break; } //检查有没有环路 for (int i 0; i n; i) { for (int j 0; j n; j) { if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]) { return false; } } } return true; }测试用例void TestGraphBellmanFord() { const char* str syztx; Graphchar, int, INT_MAX, true g(str, strlen(str)); g.AddEdge(s, t, 6); g.AddEdge(s, y, 7); g.AddEdge(y, z, 9); g.AddEdge(y, x, -3); g.AddEdge(z, s, 2); g.AddEdge(z, x, 7); g.AddEdge(t, x, 5); g.AddEdge(t, y, 8); g.AddEdge(t, z, -4); g.AddEdge(x, t, -2); vectorint dist; vectorint parentPath; if (g.BellmanFord(s, dist, parentPath)) { cout endl; g.PrinrtShotPath(s, dist, parentPath); } else { cout 存在负权回路 endl; } }结果下面我们来说一说这个算法比较难理解的点为什么外面要套一层for(int k0;kn-1;k)即为什么循环 n‑1 次首先先记住每一次循环指的是最外面k的一次循环进去都会重新把所有的边都尝试松弛即一次大循环---尝试松弛所有边1.先从拿边顺序的角度好理解我们先来看一个例子一个链图1→2→3n3n‑12情况 A边顺序[1→2 , 2→3]第一轮外层循环先松弛1→2dist[2]1紧接着松弛2→3直接用刚刚改好的 dist [2]dist [3]2仅仅 1 轮外层循环全部算完。updatedtrue不会 break。进入第二轮所有边都松弛不动updatedfalsebreak 跳出。实际有效工作只做了 1 轮。情况 B边顺序[2→3 , 1→2]第一轮外层循环先松弛2→3dist [2] 是无穷什么也做不了再松弛1→2dist[2]1第一轮结束dist [3] 依旧无穷。注意已经遍历过的边不会回头重新跑2→3已经处理完毕本轮不会再回来处理它。只能等下一轮大循环。第二轮外层循环 再次全部遍历边处理2→3dist [3] 才更新。这里实打实需要 2 轮n‑1 轮。所以如果暴力依次遍历所有边做松弛操作最坏情况下每一轮循环只能松弛成功一条边。而不含负权环的情况下最短路径最多含有 (n-1) 条边那么最坏情况就要循环 (n-1) 次每轮只能松弛 1 条边即n-1次后就能确保每条边都松弛了即找到最短距离。那如果还能再松弛呢为什么又说不含负权环的情况下最短路径最多含有 (n-1) 条边还能在松弛什么意思意思说我还能找到更短的路径可是按理说我n-1次循环下来n-1条边都已经松弛过了已经是最短的路径了呀。所以只能说明总的边数不是n-1而是存在环那到底是正权环还是负权环答案肯定是负权环因为只有负数才能使路径减小呀才能继续松弛下去。所以也能解释如果没有负权环的情况下最短路径最多就只有n-1条边2.我们也可以从具体的过程来理解再次看到打印结果我们分析一下依次选出的边看看哪里有问题所以在dist[t]2松弛更新后应该再用新更新的dist[t]2再对dist[z]松弛更新呀。即就只能等下一次循环进来后又一次对每一条边进行松弛的时候完成了这一次用的就是这个新的dist了。同样的这只是这1条边发生了这样的情况要是不带负权环一共n-1条边呢那就一共就需要n-1次循环补充双数组DP 原版才是符合 Bellman-Ford 数学定义斯坦福 / MIT 算法讲义的标准定义版本性质同一轮内永远只用本轮开始前的旧距离本轮新更新的值本轮不能复用struct Edge { int u, v, w; // u起点v终点w边权 } edges[M]; int old_dist[N]; // 上一轮迭代结束后的距离数组本轮全程只读不能修改 int new_dist[N]; // 保存本轮松弛计算出来的新距离 int n, m, s; // n顶点数量m边数s起点 // Bellman-Ford算法返回true代表图存在负权回路false无负环 bool bellman_ford() { // 初始化距离数组0x3f代表无穷大起点距离设为0 memset(old_dist, 0x3f, sizeof old_dist); old_dist[s] 0; // 最多循环 n-1 轮最短路径最多包含 n-1 条边 for(int i 1; i n - 1; i) { //① 本轮开始把旧距离拷贝到new_distnew_dist初始等于上一轮结果 memcpy(new_dist, old_dist, sizeof new_dist); // 遍历全部m条边做松弛操作 for(int j 0; j m; j) { int u edges[j].u; int v edges[j].v; int w edges[j].w; // 如果u可达并且经过u到v的路径更短 if(old_dist[u] ! 0x3f3f3f3f new_dist[v] old_dist[u] w) { new_dist[v] old_dist[u] w; // 更新v的最短距离 } } bool updated false; //标记本轮有没有任何点的距离被更新 for(int k 1; k n; k) if(new_dist[k] ! old_dist[k]) { updated true; break; } //② 本轮全部边松弛完毕把本轮结果保存到old_dist作为下一轮的旧距离 memcpy(old_dist, new_dist, sizeof old_dist); if(!updated) break; //本轮没有任何更新提前退出后面不会再优化了 } // 负环检测 // 再遍历一遍所有边如果还能松弛说明存在负权回路 for(int j 0; j m; j) { int u edges[j].u; int v edges[j].v; int w edges[j].w; if(old_dist[u] ! 0x3f3f3f3f old_dist[v] old_dist[u] w) { return true; // 还能松弛存在负权环 } } return false; //无负环 }2次memcpy只读取 old_dist旧数组只写入 new_dist新数组第一次memcpynew_dist ← old_dist含义 本轮一开始先把上一轮的结果全部复制一份给 new_dist。就像是换个名字在new_dist的基础上修改不去改old第二次memcpyold_dist ← new_dist含义本轮所有边处理完毕本轮的全部计算结果都存在 new_dist 里现在把本轮的最终结果整体拷贝到 old_dist作为下一轮迭代的 “旧基准数组”。和 原版DP 公式对应d(k)[v] min( d(k-1)[v], d(k-1)[u]w )• d(k−1) → old_dist• d(k) → new_dist第一次 memcpyd (k)[v] 初始化为 d (k−1)[v]第二次 memcpy本轮计算完成把 d (k) 交给 old_dist作为下一轮的 d (k−1)重点是通过这个双数组的方式我们能很好理解为什么要n-1次循环。3 个顶点 n3s → t → z边权都是 1顶点stz边s→t (1)t→z (1) n3所以最多循环n-12 轮初始old_dist [0, ∞, ∞]s 起点距离 0t、z 无穷大第 1 轮k1最多走 1 条边memcpyo-n)new_dist [0, ∞, ∞]遍历所有边s→told_dist[s]1 011 ∞ → new_dist[t]1t→zold_dist [t] 是∞无法更新本轮结束memcpy 把 new_dist 给 old_dist 现在 old_dist [0, 1, ∞] 本轮算出最多 1 条边能到达的点t第 2 轮k2最多走 2 条边memcpynew_dist [0, 1, ∞]遍历所有边s→told_dist [s]11不比 new_dist [t] 更小不变t→zold_dist[t]1 112 ∞ → new_dist[z]2本轮结束memcpyold_dist [0,1,2] 本轮算出最多 2 条边到达 z现在 2 轮跑完n-12所有简单路径全部算完。 简单路径不能重复经过顶点3 个点最多 2 条边不可能存在 3 条边的无重复点路径。如果再跑第 3 轮k3再次遍历边已经找不到可以松弛更新的点了距离不会再变小。如果第 3 轮还能更新说明图里存在负环。总结每一轮外层循环只能基于上一轮old_dist多拓展1 条边。本轮内部产生的新距离本轮不能拿来用下一轮才生效。第 1 轮只能算出最多1 条边的路径源点直接相连第 2 轮可以算出最多2 条边的路径…第 k 轮可以算出最多k 条边的路径想要算出拥有 n‑1 条边的那条最长无环路径就必须执行到第 n‑1 轮。每次循环只能往外扩展1条边n-1条边就要n-1次循环2者对比效率单数组更高双数组绝大多数情况必须跑满 n-1 次如果有不可达的情况就直接break了虽然也不用一定要n-1次但情况很少eg链图 1→2→3n3单数组边顺序1→22→31 轮全部更新完第二轮直接 break总共 2 轮循环但第二轮只是扫一遍很快退出双数组第 1 轮只能更新点 2第 2 轮才能更新点 3。两轮跑完才全部更新完成无法压缩到 1 轮