c++ Bellman-Ford算法的具體實現(xiàn)

更新時間：2021年06月28日 15:20:46 作者：即使敵眾我寡

Bellman-Ford算法用于解決有邊數(shù)限制的最短路問題，且可以應對有負邊權(quán)的圖，本文主要介紹了c++ Bellman-Ford算法的具體實現(xiàn)，感興趣的可以了解一下

Bellman-Ford算法用于解決有邊數(shù)限制的最短路問題，且可以應對有負邊權(quán)的圖

其時間復雜度為O(nm)，效率較低

代碼實現(xiàn)：

#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號點之間找到一條經(jīng)過小于等于k條邊的通路
//dis：各點到源點的距離，backup：備份 
struct Node
{
	int x,y,v;
}edge[N];//可以直接用結(jié)構(gòu)體存邊 
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備份數(shù)組存在的意義：每一次“迭代”后，實現(xiàn)對dis數(shù)組的當前狀態(tài)進行保存

這里詳細解釋一下“迭代”的含義：此處的迭代即為從源點開始，對所到達的點的出邊進行松弛

舉個例子：有一個如下的圖，1號點為源點