快捷導(dǎo)航

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

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

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

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

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

代碼實(shí)現(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個點(diǎn)，在1號點(diǎn)到n號點(diǎn)之間找到一條經(jīng)過小于等于k條邊的通路
//dis：各點(diǎn)到源點(diǎn)的距離，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;
 }

對代碼中的重難點(diǎn)的解釋：

1.backup備份數(shù)組存在的意義：每一次“迭代”后，實(shí)現(xiàn)對dis數(shù)組的當(dāng)前狀態(tài)進(jìn)行保存

這里詳細(xì)解釋一下“迭代”的含義：此處的迭代即為從源點(diǎn)開始，對所到達(dá)的點(diǎn)的出邊進(jìn)行松弛

舉個例子：有一個如下的圖，1號點(diǎn)為源點(diǎn)

第一次迭代

找到2,3號點(diǎn)到源點(diǎn)的最短距離

第二次迭代

找到4,5號點(diǎn)到源點(diǎn)的最短距離

第三次迭代

由于所有邊都已被遍歷，沒有邊能夠被松弛，迭代結(jié)束

由剛才的過程可知，每一次迭代后要對dis數(shù)組進(jìn)行備份，若一直使用dis數(shù)組進(jìn)行運(yùn)算，程序則會失去迭代的控制（在代碼中迭代體現(xiàn)為Bellman-Ford函數(shù)中的外重循環(huán)，題目要求最多經(jīng)過k條邊，實(shí)際上就是最多有k次迭代）

2.代碼的最后的判斷

為什么是if(dis[n]>inf/2)，而不是if(dis[n]==inf)呢？

原因是Bellman-Ford算法可能處理含負(fù)權(quán)邊的圖，dis[n]可能會出現(xiàn)+∞-2這樣的數(shù)值，所以進(jìn)行大小比較判斷時條件只需要讓dis[n]大于一個同數(shù)量級的數(shù)（此處為inf/2）即可

到此這篇關(guān)于c++ Bellman-Ford算法的具體實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)c++ Bellman-Ford內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: