c++|c++ Bellman-Ford算法的具体实现
Bellman-Ford算法用于解决有边数限制的最短路问题，且可以应对有负边权的图
其时间复杂度为O(nm)，效率较低
文章图片
代码实现：
#include#include #include#define inf 0x3f3f3f3fusing namespace std; const int N=1e4+10; const int M=510; int m,n,k,dis[M],backup[M]; //m条边，n个点，在1号点到n号点之间找到一条经过小于等于k条边的通路//dis：各点到源点的距离，backup：备份 struct Node{ int x,y,v; }edge[N]; //可以直接用结构体存边 int Bellman_Ford(){dis[1]=0; memset(dis,0x3f,sizeof dis); for(int i=1; i<=k; i++) {memcpy(backup,dis,sizeof dis); for(int j=1; j<=m; j++){Node t=edge[j]; dis[t.y]=min(dis[t.y],backup[t.x]+t.v); } } if(dis[n]>inf/2) return -1; return dis[n]; }int main(){ cin>>n>>m>>k; for(int i=1; i<=m; i++) {int a,b,c; cin>>a>>b>>c; edge[i]={a,b,c}; } int ans=Bellman_Ford(); if(ans==-1)cout<<"impossible"; elsecout< 对代码中的重难点的解释：
1.backup备份数组存在的意义：每一次“迭代”后，实现对dis数组的当前状态进行保存
这里详细解释一下“迭代”的含义：此处的迭代即为从源点开始，对所到达的点的出边进行松弛
举个例子：有一个如下的图，1号点为源点
文章图片
第一次迭代
找到2,3号点到源点的最短距离
文章图片
第二次迭代
找到4,5号点到源点的最短距离
文章图片
第三次迭代
由于所有边都已被遍历，没有边能够被松弛，迭代结束
由刚才的过程可知，每一次迭代后要对dis数组进行备份，若一直使用dis数组进行运算，程序则会失去迭代的控制（在代码中迭代体现为Bellman-Ford函数中的外重循环，题目要求最多经过k条边，实际上就是最多有k次迭代）
2.代码的最后的判断
为什么是if(dis[n]>inf/2)，而不是if(dis[n]==inf)呢？
原因是Bellman-Ford算法可能处理含负权边的图，dis[n]可能会出现+∞-2这样的数值，所以进行大小比较判断时条件只需要让dis[n]大于一个同数量级的数（此处为inf/2）即可
【c++|c++ Bellman-Ford算法的具体实现】到此这篇关于c++ Bellman-Ford算法的具体实现的文章就介绍到这了,更多相关c++ Bellman-Ford内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- opencv|opencv C++模板匹配的简单实现
- 一个选择排序算法
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列