《Bellman-ford算法.ppt》由会员分享,可在线阅读,更多相关《Bellman-ford算法.ppt(13页珍藏版)》请在三一文库上搜索。
1、Bellman-Ford算法: 为了能够求解边上带有负值的单源最短路径问题,Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点,以缩短到达终点的最短路径长度的方法。,Bellman-Ford算法的限制条件: 要求图中不能包含权值总和为负值回路(负权值回路),如下图所示。Why?,Bellman-Ford算法,Bellman-Ford算法思想,Bellman-Ford算法构造一个最短路径长度数组序列dist 1 u, dist 2 u, , dist n-1 u。其中: dist 1 u为从源点v到终点u的只经过一条边的最短路径长度,并有dist 1 u =Edgevu; d
2、ist 2 u为从源点v最多经过两条边到达终点u的最短路径长度; dist 3 u为从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度; dist n-1 u为从源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度; 算法的最终目的是计算出dist n-1 u,为源点v到顶点u的最短路径长度。,dist k u的计算,采用递推方式计算 dist k u。 设已经求出 dist k-1 u , u = 0, 1, , n-1,此即从源点v最多经过不构成负权值回路的k-1条边到达终点u的最短路径的长度。 从图的邻接矩阵可以找到各个顶点j到达顶点u的距离Edgej
3、u,计算min dist k-1 j + Edgeju ,可得从源点v绕过各个顶点,最多经过不构成负权值回路的k条边到达终点u的最短路径的长度。 比较dist k-1 u和min dist k-1 j + Edgeju ,取较小者作为dist k u的值。,递推公式(求顶点u到源点v的最短路径): dist 1 u = Edgevu dist k u = min dist k-1 u, min dist k-1 j + Edgeju , j=0,1,n-1,ju,例子,dist 2 1 = min dist 1 1, min dist 1 j + Edgej1 = min6, mindist1
4、0+Edge01, dist12+Edge21, ,算法实现,#define MAX_VER_NUM 10 /顶点个数最大值 #define MAX 1000000 int EdgeMAX_VER_NUMMAX_VER_NUM; /图的邻接矩阵 int vexnum; /顶点个数 void BellmanFord(int v) /假定图的邻接矩阵和顶点个数已经读进来了 int i, k, u; for(i=0; ivexnum; i+) disti=Edgevi; /对dist 初始化 if( i!=v ,注意: 本算法使用同一个数组dist u来存放一系列的dist k u 。其中k = 0
5、, 1, , n-1。算法结束时中存放的是dist n-1 u 。 path数组含义同Dijkstra算法中的path数组。,for(k=2; kdisti+Edgeiu ) distu=disti+Edgeiu; pathu=i; ,如果dist 各元素的初值为MAX,则循环应该n-1次,即k的初值应该改成1。,Dijkstra算法与Bellman算法的区别,Dijkstra算法和Bellman算法思想有很大的区别: Dijkstra算法在求解过程中,源点到集合S内各顶点的最短路径一旦求出,则之后不变了,修改的仅仅是源点到T集合中各顶点的最短路径长度。 Bellman算法在求解过程中,每次循
6、环都要修改所有顶点的dist ,也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。,如果存在从源点可达的负权值回路,则最短路径不存在,因为可以重复走这个回路,使得路径无穷小。 在Bellman算法中判断是否存在从源点可达的负权值回路的方法:,思路:在求出distn-1 之后,再对每条边判断一下:加入这条边是否会使得顶点v的最短路径值再缩短,即判断: distu+w(u,v)distv 是否成立,如果成立,则说明存在从源点可达的负权值回路。代码如下:,for (i=0;idisti+Edgeij) return 0;/存在从源点可达的负权值回路 return 1;,算法复
7、杂度分析,假设图的顶点个数为n,边的个数为e。算法中有一个三重嵌套的for循环,如果: 使用邻接矩阵存储图,最内层if语句的总执行次数为O(n3),因此算法的复杂度为O(n3); 使用邻接表存储图,内层的两个for循环改成while循环,可以使算法的复杂度降为O(n*e)。,Bellman-Ford算法思想的另一种理解,前面已经提到:如果使用邻接表存储图,内层的两个for循环改成while循环,可以使算法的复杂度降为O(n*e)。邻接表里直接存储了边的信息,浏览完所有的边,复杂度是O(e)。而邻接矩阵是间接存储边,浏览完所有的边,复杂度是O(n2)。,具体描述:对图中的每条有向边,权值为w,如
8、果distu+w的引入,会缩短源点v0到顶点v的最短路径长度,那么应该修改distv,修改成distu+w。,#define MAX 999999 #define EDGE_MAX 100 /边数最大值 #define VER_MAX 50 /顶点个数最大值 struct Edge int u, v, w; /边:起点、终点、权值 ; Edge edgesEDGE_MAX; /存储所有的边 int m; /实际边的个数 int n; /顶点个数 /* dist为源点v0到各顶点的最短距离,如果初始为v0到各顶点直接边的长度,则 算法中的循环要执行n-2次,如果初始为MAX,则循环要执行n-1次
9、,第一次求得的 dist就是v0到各顶点直接边的长度 */ int distVER_MAX=MAX; /假定边的数组、边的个数这些信息已经读进来了,假设图中有关边的数据结构如下:,实现(具体应用见ZOJ2770的代码),bool bellman_ford()/bellman-ford算法 int i, k, t; for(i = 1; i n; i +) /*假设第k条边的起点是u,终点是v,以下循环考虑第k条边是否会使得源点v0到v的 最短距离缩短,即判断distedgesk.u + edgesk.w distedgesk.v 是否成立*/ for(k = 0; k m; k +) t = distedgesk.u + edgesk.w; if(distedgesk.u != mx ,Bellman-Ford算法改进,Bellman-Ford算法是否一定要循环n-2次,n为顶点个数。 未必!其实只要在某次循环过程中,考虑每条边后,都没能改变当前源点到所有顶点的最短路径长度,那么Bellman-Ford算法就可以提前结束了。 详见ZOJ 1508的代码。,
链接地址:https://www.31doc.com/p-2890163.html