bellman-ford算法

1Bellman-Ford算法：为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。Bellman-Ford算法的限制条件：要求图中不能包含权值总和为负值回路(负权值回路)，如下图所示。Why?20117-2(c)Bellman-Ford算法2Bellman-Ford算法思想Bellman-Ford算法构造一个最短路径长度数组序列dist1[u],dist2[u],…,distn-1[u]。其中：dist1[u]为从源点v到终点u的只经过一条边的最短路径长度，并有dist1[u]=Edge[v][u]；dist2[u]为从源点v最多经过两条边到达终点u的最短路径长度；dist3[u]为从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度；……distn-1[u]为从源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度；算法的最终目的是计算出distn-1[u]，为源点v到顶点u的最短路径长度。3distk[u]的计算采用递推方式计算distk[u]。设已经求出distk-1[u],u=0,1,…,n-1，此即从源点v最多经过不构成负权值回路的k-1条边到达终点u的最短路径的长度。从图的邻接矩阵可以找到各个顶点j到达顶点u的距离Edge[j][u]，计算min{distk-1[j]+Edge[j][u]}，可得从源点v绕过各个顶点，最多经过不构成负权值回路的k条边到达终点u的最短路径的长度。比较distk-1[u]和min{distk-1[j]+Edge[j][u]}，取较小者作为distk[u]的值。递推公式(求顶点u到源点v的最短路径)：dist1[u]=Edge[v][u]distk[u]=min{distk-1[u],min{distk-1[j]+Edge[j][u]}},j=0,1,…,n-1,j≠u4461230565-2-25-1-1133(c)6543210030301021021055606543210kdistk[0]distk[1]distk[2]distk[3]distk[4]distk[5]distk[6]10655∞∞∞2033554∞30135247401350455013504360135043例子dist2[1]=min{dist1[1],min{dist1[j]+Edge[j][1]}}=min{6,min{dist1[0]+Edge[0][1],dist1[2]+Edge[2][1],…}}5算法实现#defineMAX_VER_NUM10//顶点个数最大值#defineMAX1000000intEdge[MAX_VER_NUM][MAX_VER_NUM];//图的邻接矩阵intvexnum;//顶点个数voidBellmanFord(intv)//假定图的邻接矩阵和顶点个数已经读进来了{inti,k,u;for(i=0;ivexnum;i++){dist[i]=Edge[v][i];//对dist[]初始化if(i!=v&&dis[i]MAX)path[i]=v;//对path[]初始化elsepath[i]=-1;}注意：1.本算法使用同一个数组dist[u]来存放一系列的distk[u]。其中k=0,1,…,n-1。算法结束时中存放的是distn-1[u]。2.path数组含义同Dijkstra算法中的path数组。6for(k=2;kvexnum;k++)//从dist1[u]递推出dist2[u],…,distn-1[u]{for(u=0;uvexnum;u++)//修改每个顶点的dist[u]和path[u]{if(u!=v){for(i=0;ivexnum;i++)//考虑其他每个顶点{if(Edge[i][u]MAX&&dist[u]dist[i]+Edge[i][u]){dist[u]=dist[i]+Edge[i][u];path[u]=i;}}}}}}如果dist[]各元素的初值为MAX，则循环应该n-1次，即k的初值应该改成1。7Dijkstra算法与Bellman算法的区别§Dijkstra算法和Bellman算法思想有很大的区别：Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。8如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。在Bellman算法中判断是否存在从源点可达的负权值回路的方法：思路：在求出distn-1[]之后，再对每条边u,v判断一下：加入这条边是否会使得顶点v的最短路径值再缩短，即判断：dist[u]+w(u,v)dist[v]是否成立，如果成立，则说明存在从源点可达的负权值回路。代码如下：for(i=0;in;i++){for(j=0;jn;j++){if(Edge[i][j]MAX&&dist[j]dist[i]+Edge[i][j])return0;//存在从源点可达的负权值回路}}return1;9算法复杂度分析§假设图的顶点个数为n，边的个数为e。算法中有一个三重嵌套的for循环，如果：使用邻接矩阵存储图，最内层if语句的总执行次数为O(n3)，因此算法的复杂度为O(n3)；使用邻接表存储图，内层的两个for循环改成while循环，可以使算法的复杂度降为O(n*e)。10Bellman-Ford算法思想的另一种理解前面已经提到：如果使用邻接表存储图，内层的两个for循环改成while循环，可以使算法的复杂度降为O(n*e)。邻接表里直接存储了边的信息，浏览完所有的边，复杂度是O(e)。而邻接矩阵是间接存储边，浏览完所有的边，复杂度是O(n2)。具体描述：对图中的每条有向边u,v，权值为w，如果dist[u]+wdist[v]，即有向边u,v的引入，会缩短源点v0到顶点v的最短路径长度，那么应该修改dist[v]，修改成dist[u]+w。11#defineMAX999999#defineEDGE_MAX100//边数最大值#defineVER_MAX50//顶点个数最大值structEdge{intu,v,w;//边：起点、终点、权值};Edgeedges[EDGE_MAX];//存储所有的边intm;//实际边的个数intn;//顶点个数/*dist为源点v0到各顶点的最短距离,如果初始为v0到各顶点直接边的长度,则算法中的循环要执行n-2次，如果初始为MAX，则循环要执行n-1次，第一次求得的dist就是v0到各顶点直接边的长度*/intdist[VER_MAX]={MAX};//假定边的数组、边的个数这些信息已经读进来了假设图中有关边的数据结构如下：实现(具体应用见ZOJ2770的代码)12boolbellman_ford()//bellman-ford算法{inti,k,t;for(i=1;in;i++){/*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的最短距离缩短,即判断dist[edges[k].u]+edges[k].wdist[edges[k].v]是否成立*/for(k=0;km;k++){t=dist[edges[k].u]+edges[k].w;if(dist[edges[k].u]!=mx&&tdist[edges[k].v]){dist[edges[k].v]=t;}}}/*以下是检查，若还有更新则说明存在无限循环的负值回路*/for(k=0;km;k++){if(dist[edges[k].u]!=MAX&&dist[edges[k].u]+edges[k].wdist[edges[k].v]){returnfalse;}}returntrue;}13Bellman-Ford算法改进Bellman-Ford算法是否一定要循环n-2次，n为顶点个数。未必！其实只要在某次循环过程中，考虑每条边后，都没能改变当前源点到所有顶点的最短路径长度，那么Bellman-Ford算法就可以提前结束了。详见ZOJ1508的代码。