Bellman-Ford算法

Bellman-Ford算法是用來解決,對于有負權的圖的**單源最短路徑**.因為DJ算法不可以解決對于負權的圖,所以使用這個算法來求解.但是依舊不可以有負回路.因為負回路就沒有存在單源最短路徑這一說.

BF的另一個重要的用途就是用來檢測**是不是存在負回路**

思路:

• 就是考察每一條邊,假設為邊的源頭是a,邊的終點是b,邊的權重是len.那么考察這條邊所能到達的點b,如果存在dis[a]!=INT_MAX && dis[a]+len<dis[b],那么就說明可以松弛.其中dis[index]表示源點到index的最短距離.

• 所以采用**邊集數組**來存圖.邊的遍歷順序可以隨便指定.

• 思考最壞的遍歷的情況,每一次遍歷,只能有一個點可以通過松弛操作,把dis[index]更新,那么n個點就需要n-1次松弛操作.因為(源點到源點的距離為0不需要更新)

• 所以從上述的描述可以看出,算法的時間復雜度為$\text{O}(V\times M)$其中V為點的數量,M為邊的數量.

• 如果進行完成V*M之后還可以再進行一次松弛操作就是還存在dis[a]!=INT_MAX && dis[a]+len<dis[b].那么就是存在負環.

• 如果是用來檢測從某個點是不是可以到達負回路(負環).就初始化dis[src]=0,其余的值都為無窮大,

• 但是如果要判斷整個圖是不是存在負回路的話就要使用到虛擬源點的思路.

• 具體來說就是初始化dis[ALL]=0設置一個虛擬源點到所有的點的距離為0.就是和所有的點都有連接.

注意:

判斷整個圖是不是存在負環和判斷從src出發是不是存在負環,是不一樣.因為從src可能壓根就達到不了那個負環,就是圖不是連通的那么就非常有可能**判斷不出來那個負環.**

就是關于Bellman-ford算法必須知道的幾個最:

• 最多進行點數-1輪所有邊的松弛,就可以更新所有的最短路徑.因為最壞的情況下就是遍歷完成所有的邊之后只能更新一個點的最短路徑.
• 每個點最多被松弛點數-1次.如果進行了點數次松弛說明就有負環.因為考察每條邊的次數是點數-1輪.每一輪都會遍歷所有的邊.所以存在每一次都會松弛這個點一次的情況.

代碼:

dis數組存儲單源最短路徑,并且判斷是不是可以到達負環.(不能判斷整個圖是不是存在負環)

#include <bits/stdc++.h>
using namespace std;
struct Edge
{int u,v,len;
};
int dis[10003];
int main()
{int n,m;cin>>n>>m;int start=0;cin>>start;Edge edges[m+2];for(int i=0;i<m;i++){cin>>edges[i].u>>edges[i].v>>edges[i].len;}int dis[n+2];for(int i=0;i<n;i++){dis[i]=INT_MAX;}dis[start]=0;bool flag=false,huan=false;for(int i=0;i<n-1;i++){flag=false;for(int j=0;j<m;j++){if(dis[edges[j].u]!=INT_MAX&&dis[edges[j].v]>dis[edges[j].u]+edges[j].len){flag=true;dis[edges[j].v]=dis[edges[j].u]+edges[j].len;}}if(flag==false)break;//如果沒有存在松弛操作就可以提前退出了}if(flag==false){//在進行一次遍歷,看一看是不是還存在松弛的點for(int j=0;j<m;j++){if(dis[edges[j].u]!=INT_MAX&&dis[edges[j].v]>dis[edges[j].u]+edges[j].len){huan=true;break;}}if(huan)cout<<"有負環"<<endl;}return 0;
}

如果判斷圖中是不是存在負環,除了要設置虛擬源點外還要**進行V次松弛操作**.因為點都要出來;代碼如下:

#include <bits/stdc++.h>
using namespace std;
struct Edge
{int u,v,len;
};
int dis[10003];
int main()
{int n,m;cin>>n>>m;int start=0;cin>>start;Edge edges[m+2];for(int i=0;i<m;i++){cin>>edges[i].u>>edges[i].v>>edges[i].len;}int dis[n+2];for(int i=0;i<n;i++){dis[i]=0;}dis[start]=0;bool flag=false,huan=false;for(int i=0;i<n;i++){flag=false;for(int j=0;j<m;j++){if(dis[edges[j].u]!=INT_MAX&&dis[edges[j].v]>dis[edges[j].u]+edges[j].len){flag=true;dis[edges[j].v]=dis[edges[j].u]+edges[j].len;}}if(flag==false)break;//如果沒有存在松弛操作就可以提前退出了}if(flag==false){//在進行一次遍歷,看一看是不是還存在松弛的點for(int j=0;j<m;j++){if(dis[edges[j].u]!=INT_MAX&&dis[edges[j].v]>dis[edges[j].u]+edges[j].len){huan=true;break;}}if(huan)cout<<"有負環"<<endl;}return 0;
}

如果對建圖的知識還不了解的話,可以參考我寫的這篇高質量博客(但是不知道為什么觀看量不太高,明明很好.)文章鏈接:

建圖大法好
一定要好好的揣摩我寫的這篇建圖博客,一定會對你有所幫助的.

上述中常數時間可以被優化一下,就是利用隊列來優化一下,有時候并不會要求對所有的邊都需要進行考察,而是對于那些有了松弛的點所連接的邊才需要進行下一輪的松弛考察.因為這個點被松弛了,所以從他開始的邊所達到的點,才有可能被松弛.所以只考察,被松弛的點所連接的邊即可.因為設計到點所連接的邊.所以使用領接表建圖.不在使用邊集數組.

測試鏈接

SPFA優化如下:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
//首先建圖,使用鄰接表建圖,u=pair.first,v=pair.second.
//遍歷所有的邊.dis[v]=min(dis[v],dis[u]+arr[u][i].second
inline ll read()
{ll f = 0, s = 0;char ch = getchar();while (!isdigit(ch)) f |= ch == '-', ch = getchar();while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();return f ? -s : s;
}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int main()
{int ci;cin>>ci;while(ci--){int n,m;cin>>n>>m;vector<PII>arr[n+2];int dis[n+2];int dui[4000002];int l=0,r=0;bool flag[n+1];//建圖for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;if(c>=0){arr[a].push_back({b,c});arr[b].push_back({a,c});}elsearr[a].push_back({b,c});}//初始化數組for(int i=1;i<=n;i++){dis[i]=INT_MAX;flag[i]=false;}//將源點放進隊列dis[1]=0;dui[r++]=1;flag[1]=true;bool ans=false;int cnt[n+2]={0};//統計每個點被松弛的次數,更新距離才算松弛cnt[1]++;//因為1距離更新了while(l!=r){int index=dui[l++];flag[index]=false;for(int i=0;i<arr[index].size();i++){if(dis[index]!=INT_MAX&&dis[index]+arr[index][i].second<dis[arr[index][i].first]){dis[arr[index][i].first]=dis[index]+arr[index][i].second;//距離更新了所以要,將松弛次數++if(cnt[arr[index][i].first]++ == n){ans=true;break;}if(flag[arr[index][i].first]==false){dui[r++]=arr[index][i].first;flag[arr[index][i].first]=true;}}}if(ans)break;}if(ans)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}