Bellman_Ford算法:
Bellman_Ford 算法解决的是一般情况下的单源最短路径问题，其边可以为负值。Bellman_Ford算法可以判断图是否存在负环，若存在负环会返回一个布尔值。当然在没有负环存在的情况下会返回所求的最短路径的值。时间复杂度为O(VE)。
Bellman_Ford( ) 的步骤
- 1 图的初始化等操作
- 2 for i = 1 to |G.V| - 1 // |G.V| 为图 G的点的总数
- 3 for each edge(u,v)∈G.E //G.E 为图 G 的边
- 4 relax(u,v,w)
- 5 for each edge(u,v)∈G.E
- 6 if v.d>u.d+w(u,v)
- 7 return false;
- 8 return true
此算法分为3步：
- 1）第1行对图进行初始化，初始化dis[N] = +∞,dis[s] = 0;
- 2） 第2~4行为求最短路的过程，是对图的每一条边进行|V|-1次松弛操作，求取最短路径。
- 3） 第5~8行为对每条边进行|V|-1次松弛后，检查是否存在负环并返回相应的布尔值，因为进行|V|-1次松弛后若没有负环则v.d的值确定不变，若有负环则会继续进行松弛操作，因为一个数+负数是一定比它本身要小的。
此算法的 时间复杂度为O(VE)。
为什么外层循环需要v-1次?
因为单源最短路径一定不存在环,假设最短路径含有权重为正的环,那么删去权重为正的环便得到更短的路径;如果最短路径含有权重为负的环,那么只要一直在负环里走,那么路径的权重更加小;综上,单元最短路径不存在环，所以最短路的边数最多为v-1
假设path<v0,v1,v2....vk>为 s到e的最短路径,v0=s,vk=ed，k<=v-1。算法２-4行的for循环每次松弛所有的E条边。在第i次松弛时,这里i=1,2,3,...k,被松弛的边包括边(vi-1,vi)。根据路径松弛性质,dis[ed]=s->ed的最短路权重
畅通工程续
题意:
求单源最短路径权重
#include <cstdio>
#include<cstring>
using namespace std;
const int MAXN=2010;
const int MAX=210;
const int INF=0x3f3f3f3f;
struct Node
{
int from,to,val;
Node(){}
Node(int from,int to,int val):from(from),to(to),val(val){}
};
Node edge[MAXN];
int dis[MAX];
int n,m;
void Bella_Ford(int st,int ed)
{
memset(dis,INF,sizeof(dis));
dis[st]=0;
bool flag;
for(int i=1;i<n;i++)
{
flag=true;
for(int j=0;j<m;j++)
{
if(dis[edge[j].to]>dis[edge[j].from]+edge[j].val)
{
dis[edge[j].to]=dis[edge[j].from]+edge[j].val;
flag=false;
}
}
if(flag) break;
}
if(dis[ed]==INF) printf("-1\n");
else printf("%d\n",dis[ed]);
}
int main()
{
int st,ed,u,v,val;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
edge[i]=Node(u,v,val);
edge[i+m]=Node(v,u,val);
}
m<<=1;
scanf("%d%d",&st,&ed);
Bella_Ford(st,ed);
}
return 0;
}
Wormholes
题解:
判断是否存在负环
#include<cstdio>
#include<string.h>
using namespace std;
struct Node
{
int from,to,w;
}edge[5210];
int n,m,k,dis[510],INF=0x3f3f3f3f;
bool Bellman_Ford()
{
memset(dis,INF,sizeof(dis));
dis[1]=0;
int sum=m+k;
bool flag;
for(int i=1;i<=n-1;i++)
{
flag=true;
for(int j=0;j<sum;j++)
{
int u=edge[j].from,v=edge[j].to,val=edge[j].w;
if(dis[v]>dis[u]+val)
{
dis[v]=dis[u]+val;
flag=false;
}
}
if(flag) break;
}
for(int j=0;j<sum;j++)
{
int u=edge[j].from,v=edge[j].to,val=edge[j].w;
if(dis[v]>dis[u]+val)
{
return true;
}
}
return false;
}
int main()
{
int u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
edge[i].from=u;
edge[i].to=v;
edge[i].w=val;
edge[i+m].from=v;
edge[i+m].to=u;
edge[i+m].w=val;
}
m<<=1;
for(int i=m;i<m+k;i++)
{
scanf("%d%d%d",&u,&v,&val);
edge[i].from=u;
edge[i].to=v;
edge[i].w=-val;
}
init();
if(Bellman_Ford()) printf("YES\n");
else printf("NO\n");
}
}
