Bellman-Ford算法用于解决有边数限制的最短路问题,且可以应对有负边权的图 其时间复杂度为O(nm),效率较低 代码实现: #include<iOStream&g
Bellman-Ford算法用于解决有边数限制的最短路问题,且可以应对有负边权的图
其时间复杂度为O(nm),效率较低
代码实现:
#include<iOStream>
#include<cstring>
#include<alGorithm>
#define inf 0x3f3f3f3f
using 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";
else cout<<ans;
return 0;
}
对代码中的重难点的解释:
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++ Bellman-Ford算法的具体实现的文章就介绍到这了,更多相关c++ Bellman-Ford内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: c++ Bellman-Ford算法的具体实现
本文链接: https://www.lsjlt.com/news/129312.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
一口价域名售卖能注册吗?域名是网站的标识,简短且易于记忆,为在线用户提供了访问我们网站的简单路径。一口价是在域名交易中一种常见的模式,而这种通常是针对已经被注册的域名转售给其他人的一种方式。
一口价域名买卖的过程通常包括以下几个步骤:
1.寻找:买家需要在域名售卖平台上找到心仪的一口价域名。平台通常会为每个可售的域名提供详细的描述,包括价格、年龄、流
443px" 443px) https://www.west.cn/docs/wp-content/uploads/2024/04/SEO图片294.jpg https://www.west.cn/docs/wp-content/uploads/2024/04/SEO图片294-768x413.jpg 域名售卖 域名一口价售卖 游戏音频 赋值/切片 框架优势 评估指南 项目规模
0