《算法12-最短路径-弗洛伊德Floyd算法.ppt》由会员分享，可在线阅读，更多相关《算法12-最短路径-弗洛伊德Floyd算法.ppt（16页珍藏版）》请在三一办公上搜索。
1、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有
2、弧，则从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的中间顶点
3、序号不大于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)
4、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是从
5、顶点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
6、)；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)为例，对最短路径的读法加以说明。从A(3)知，顶点1到0的最短路径长度为a10=11,其最短路径看 path10=2，path12=3，path 13=1,表示顶点0 顶点2 顶点3 顶点1;从顶点1到顶点0最短路径为,。,
