Bellman-ford算法.ppt

《Bellman-ford算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Bellman-Ford算法：为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。Bellman-Ford算法的限制条件：要求图中不能包含权值总和为负值回路(负权值回路)，如下图所示。Why?20117-2(c)Bellman-Ford算法Bellman-Ford算法思想Bellman-Ford算法构造一个最短路径长度数组序列dist1[u],dist2[u],…,distn-1[u]。其中：dist1[u]

2、为从源点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的最短路径长度。distk[u]的计算采用递推方式计算distk[u]。设已经求出distk-1[u],u

3、=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]dist

4、k[u]=min{distk-1[u],min{distk-1[j]+Edge[j][u]}},j=0,1,…,n-1,j≠u461230565-2-25-1-1133(c)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{dist

5、1[0]+Edge[0][1],dist1[2]+Edge[2][1],…}}算法实现#defineMAX_VER_NUM10//顶点个数最大值#defineMAX1000000intEdge[MAX_VER_NUM][MAX_VER_NUM];//图的邻接矩阵intvexnum;//顶点个数voidBellmanFord(intv)//假定图的邻接矩阵和顶点个数已经读进来了{inti,k,u;for(i=0;i

6、!=v&&dis[i]

7、if(u!=v){for(i=0;idist[i]+Edge[i][u]){dist[u]=dist[i]+Edge[i][u];path[u]=i;}}}}}}如果dist[]各元素的初值为MAX，则循环应该n-1次，即k的初值应该改成1。Dijkstra算法与Bellman算法的区别Dijkstra算法和Bellman算法思想有很大的区别：Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一

8、旦求出，则之后不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。在Bellman算法中判断是否存在从源点可达的负权值回路的方法：思路：在求出distn-1[]之后，再对每条边