算法12-最短路径-弗洛伊德(Floyd)算法.ppt

1,1.问题的提出：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，要求求出vi 与vj之间的最短路径和最短路径长度。,2.解决办法 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n) 方法二：弗洛伊德(Floyd)算法,2,求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕，算法结束,3. Floyd算法思想：逐个顶点试探法,从图的带权邻接矩阵G.arcs出发，假设求顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为G.arcsij的路径，但该路径是否一定是最短路径，还需要进行n次试探。,1.第一次，判别（ Vi, V0 ）和（ V0，Vj ），即判别(Vi, V0 , Vj）是否存在，若存在，则比较（ Vi, Vj ）和(Vi, V0 , Vj）的长度，取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。,2. 第二次，再加一个顶点V1，如果(Vi, , V1） 和(V1, , Vj）分别是当前找到的中间顶点序号不大于0的最短路径，那么(Vi, , V1, , Vj ）就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较，取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径。,3. 第三次，再加一个顶点V2，继续进行试探。,D(-1) =,D(-1)为有向网的邻接矩阵 第一步:以D(-1)为基础，以V0为中间顶点，求从Vi到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为(Vi,V0)+(V0,Vj) 。,D(0) ij =,minD(-1) ij, D(-1) i0+D(-1) 0j,D(0) ij 为从Vi到Vj的中间顶点序号不大于0的最短路径长度.,以D(0)为基础，以V1为中间顶点，求从Vi,到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为从Vi开始通过V0或V1到达Vj的最短路径 。,D(1) ij =,minD(0) ij, D(0) i1+D(0) 1j,以D(1)为基础，以V2为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始通过V0,V1, V2到达Vj的最短路径 。,D(2) ij =,minD(1) ij, D(1) i2+D(1) 2j,以D(2)为基础，以V3为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始通过V0,V1, V2,V3到达Vj的最短路径 。,D(3) ij =,minD(2) ij, D(2) i3+D(2) 3j,D(3) ij 即为从Vi到Vj的最短路径长度.,9,例题：,10,11,4. 论点：A(-1) ij是从顶点vi 到vj , 中间顶点是 v1的最短路径的长度,A(k) ij是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)ij是从顶点vi 到vj 的最短路径长度。 证明：归纳证明，始归纳于s (上角标); (1) 归纳基础：当s=-1 时， A(-1) ij= Edgeij, vi 到vj , 不经过任何顶点的边，是最短路径。 (2)归纳假设：当sk时， A(s) ij是从顶点vi 到vj , 中间顶点的序号不大于s的最短路径的长度; (3)当s=k时，,12,i,j,k,A(k-1) ik,A(k-1) kj,A(k-1) ij,因为：A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj 由归纳假设知： A(k-1)ij :是i到j的最短路径(标号不高于k-1)； A(k-1)ik :是i到k的最短路径(标号不高于k-1)； A(k-1)kj :是k到j的最短路径(标号不高于k-1)； 所以： A(k) ij 是i到j的最短路径(标号不高于k)。,13,图用邻接矩阵存储 edge 存放最短路径长度 pathij是从Vi到Vj的最短路径上Vj前一顶点序号,5.算法实现,void floyd ( ) for ( int i = 0; i n; i+ ) /矩阵dist与path初始化 for ( int j = 0; j n; j+ ) /置A(-1) distij = Edgeij; pathij = -1; / 初始不经过任何顶点 for ( int k = 0; k n; k+ ) /产生dist(k)及path(k) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if (distik + distkj distij ) distij = distik + distkj; pathij = k; /缩短路径, 绕过 k 到 j / floyd,14,6.算法分析： 设最内层循环体为基本操作，算法有三层循环，每层循环n次，所以T(n)=O(n3),15,16,以 Path(3)为例，对最短路径的