北京大学ACM暑期课讲义-Bellman-ford算法.pptVIP

* 信息学院信息技术教研室 Vs Vt V2 V4 V3 V1 2 4 8 4 2 7 9 1 4 6 V1 V8 V9 V10 V7 V4 V3 V6 V5 V2 图论算法理论、 实现及应用 王桂平 Bellman-Ford算法： 为了能够求解含负权边的带权有向图的单源最短路径问题，Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。不能处理带负权边的无向图。 Bellman-Ford算法的限制条件： 要求图中不能包含权值总和为负值回路(负权值回路)，如下图所示。Why? 2 0 1 1 7 -2 (c) Bellman-Ford算法 Bellman-Ford算法思想 Bellman-Ford算法构造一个最短路径长度数组序列dist 1 [u], dist 2 [u], …, dist n-1 [u]。其中： dist 1 [u]为从源点v到终点u的只经过一条边的最短路径长度，并有dist 1 [u] =Edge[v][u]； dist 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的距离Edge[j][u]，计算min{ dist k-1 [j] + Edge[j][u] } ，可得从源点v绕过各个顶点，最多经过不构成负权值回路的k条边到达终点u的最短路径的长度。 比较dist k-1 [u]和min{ dist k-1 [j] + Edge[j][u] } ，取较小者作为dist k [u]的值。 递推公式(求顶点u到源点v的最短路径)： dist 1 [u] = Edge[v][u] dist k [u] = min{ dist k-1 [u], min{ dist k-1 [j] + Edge[j][u] } }, j=0,1,…,n-1,j≠u 4 6 1 2 3 0 5 6 5 -2 -2 5 -1 -1 1 3 3 (c) k dist k [0] dist k [1] dist k [2] dist k [3] dist k [4] dist k [5] dist k [6] 1 0 6 5 5 ∞ ∞ ∞ 2 0 3 3 5 5 4 ∞ 3 0 1 3 5 2 4 7 4 0 1 3 5 0 4 5 5 0 1 3 5 0 4 3 6 0 1 3 5 0 4 3 例子 dist 2 [1] = min{ dist 1 [1], min{ dist 1 [j] + Edge[j][1] } } = min{6, min{dist1[0]+Edge[0][1], dist1[2]+Edge[2][1], … } } 算法实现 #define MAX_VER_NUM 10 //顶点个数最大值 #define MAX 1000000 int Edge[MAX_VER_NUM][MAX_VER_NUM]; //图的邻接矩阵 int vexnum; //顶点个数 int path[MAX_VER_NUM]; //path[i]是i在最短路径中的上一个节点 void BellmanFord(int v) //假定图的邻接矩阵和顶点个数已经读进来了 { int i, k, u; for(i=0; ivexnum; i++) { dist[i]=Edge[v][i]; //对dist[ ]初始化 if( i!=v dis[i]MAX ) path[i] = v; //对path[ ]初始化 else path[i] = -1; } 注意： 本算法使用同一个数组dist [u]来存放一系列的dist k [u] 。其中k = 0, 1, …, n-1。算法结束时中存放的是dist n-1 [u] 。 path数组含义同Dijkstra算法中的path数组。 for(k=2; kvexnum; k++) //从dist1[u]递推出dist2[u], …,distn-1[u] { for(u=0; u vexnum; u++)//修改每个顶点的dist[u]和path[u] {