本文主要是介绍关于Bellman-Ford的几点思考,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
关于Bellman-Ford的几点思考:
1.bellman-ford基本思想?
设s集合为,为与源点已经连接的点的集合,p为与源点不连通的集合。
开始时置s={源点},p={剩下的点};
每次操作枚举所有边把符合条件的边上的点,加入s,或者更新其dis值,直到s={所有点};
2.为什么是做n-1次松弛操作
每次松弛操作至少加一个节点加入到s中,因此松弛操作的次数的上限是n-1。
3.为什么dis[a]+w<dis[b] 就出现负回路
因为若在经过n-1次松弛操作后dis[a]+w<dis[b],dis[b]肯定在前面跟新为dis[a]+w;而现在出现了dis[a]+w<dis[b],要么dis[b]变大了,要么dis[a]变小了,而dis[b]变大是不可能的,并且w是常量,所以是dis[a]变小了。
用反证法证明:
假设不存在负回路,
而dis[a]变小了,只能存在这种情况:
---最后一次松弛操作是把d加进s,而u+v<x,dis[a]由dis[c]+x跟新为dis[c]+u+v;dis[a]刚好变小而,ab这条边在cd,da之前已经被枚举过,所以dis[b]没被跟新为dis[c]+u+v+w;所以出现了dis[a]+w<dis[b]这个情况.
然而经过n-1次松弛操作后,这种情况是不存在的。
因为在c加入s后,cd这条边满足条件(dis[c]+u<dis[d](dis[d]初始话为无穷)),d可以直接加入s中,
设c是第k次加入s中的,
若在第k次中,cd是在c已经加入s中后再枚举的,那么在第k次中,d被直接加入到s中,
若在第k次中,cd已经在c加入s中前已经枚举过,那么在第k+1次中,d被加入到s中;
所以若d是第n-1次松弛操作的时候加进s的,那么c肯定最早是在第n-2次加入s的。
设c是通过Cic这条边连到s的,ci是通过ci-1连到s的,ci-2...
若c是最早是在第n-2次加入的,那么ci最早是在第n-3次加入的,那么ci-2.....
C1最早是在第0次加入的(c1是源点),所以i》=n-3+1,即i>=n-2;而节点总共只有n个,除去c和d,那么a和b肯定是c1到ci中的某两个点,那么c肯定和a,b构成了回路,
而a在c的前面,
若a到c经过的边中没有负边,那么dis[c]>=dis[a],而a又通过c,dis[a]被更新为dis[c]+x,即dis[c]+x<dis[a],推出x<0,所以在a,c所在回路中出现了负边,即出现了负回路,与假设矛盾。
若a到c经过的边中出现了负边,那么也出现了负回路,与假设矛盾。
Bellman-ford算法代码:
Dis[i]为i到源点的距离,edges为结构体,edges.a到edges.b的权值是edges.w。
int relax(int u,int v,int w)
{
if (dis[u]+w<dis[v])
{
dis[v]:=dis[u]+w;
pre[v]:=u;
}
}
bool bellman_ford()
{
int i,j;
for(i=1;i<=n-1;i++)
for(j=1;j<=e;j++)
relax(edges[j].a,edges[j].b,edges[j].w);
for(i=1;i<=e;i++)
if (dis[edges[i].a]+w<dis[edges[i].b]) return false;//出现负回路
return true;
}
这篇关于关于Bellman-Ford的几点思考的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!