c++(Bellman?Ford算法的具体实现)

c++,Bellman?Ford算法的具体实现

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内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧！