单源最短路,顾名思义,就是从一个起点到其余点的最短距离
Bellman-Ford算法的思路是进行至多n-1轮的更新,每次遍历所有的边,进行松弛操作d[v]=min(d[v],d[u]+w);
Bellman-Ford算法可以处理有负边权的图,也可以判负环,只要在第n轮还能进行松弛操作,说明存在负环
例题 洛谷P3371 【模板】单源最短路径(弱化版)
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#define forup(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
vector<pair<int,int>> node[100005];
int d[100005];
int n,m,s;
void bellmanford(int s)
{
d[s]=0;
bool done;//记录某一轮是否进行了更新
forup(i,1,n)//对每一条边都进行访问
{
done=false;
forup(u,1,n)
{
if(!~d[u]) continue;//还没有更新过最短路,不可用
for(auto x:node[u])
{
int v=x.first,w=x.second;
if(d[u]+w<d[v]||d[v]==-1) d[v]=d[u]+w,done=true;//松弛操作,距离更短或没有过最短路就更新
}
}
if(!done) return ;//没有更新,说明都是最短路
}
}
int main()
{
cin>>n>>m>>s;
int u,v,w;
forup(i,1,m){
cin>>u>>v>>w;
node[u].push_back({v,w});
}
memset(d,-1,sizeof(d));//-1的话取反就是0了,还是比较方便的
bellmanford(s);
forup(i,1,n)
if(!~d[i]) cout<<2147483647<<' ';
else cout<<d[i]<<' ';
return 0;
}
参考:https://www.cnblogs.com/dx123/p/16320435.html
标签:forup,int,单源,Bellman,Ford,include From: https://www.cnblogs.com/V-sama/p/17422894.html