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;
}