算法最短路径弗洛伊德Floyd算法.pptx

《算法最短路径弗洛伊德Floyd算法.pptx》由会员分享，可在线阅读，更多相关《算法最短路径弗洛伊德Floyd算法.pptx（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1求最短路径步骤求最短路径步骤初始时设置一个初始时设置一个n n阶方阵，令其对角线元素为阶方阵，令其对角线元素为0 0，若存在弧，若存在弧，则对应元素为权值；否则，则对应元素为权值；否则为为 逐步试着在原直接路径中增加中间顶点，若加逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持入中间点后路径变短，则修改之；否则，维持原值原值所有顶点试探完毕，算法结束所有顶点试探完毕，算法结束3.Floyd算法思想：逐个顶点试探法第1页/共16页 从图的带权邻接矩阵从图的带权邻接矩阵G.arcs出发，假设求出发，假设求顶点顶点Vi到到Vj的最短路径。如果从的最短路径。如果从Vi

2、到到Vj有弧，有弧，则从则从Vi到到Vj存在一条长度为存在一条长度为G.arcsij的路的路径，但该路径是否一定是最短路径，还需要径，但该路径是否一定是最短路径，还需要进行进行n次试探。次试探。1.第一次，判别（Vi,V0）和（V0，Vj ），即判别(Vi,V0,Vj）是否存在，若存在，则比较（Vi,Vj）和(Vi,V0,Vj）的长度，取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。第2页/共16页 2.第二次，再加一个顶点V1，如果(Vi,V1）和(V1,Vj）分别是当前找到的中间顶点序号不大于0的最短路径，那么(Vi,V1,Vj）就有可能是从Vi到Vj的中间顶点序号不大于1的最

3、短路径。将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较，取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径。3.第三次，再加一个顶点V2，继续进行试探。第3页/共16页V2V3V0V1123456890 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888D(-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)0j47D(0)=D(0)ij 为从

4、Vi到Vj的中间顶点序号不大于中间顶点序号不大于0 0的最短路径长度.V0第4页/共16页V2V3V0V112345689 以D(0)为基础，以V1为中间顶点，求从Vi,到Vj的最短路径。该路径或者为从Vi到Vj的边,或者为从Vi开始通过V0或V1到达Vj的最短路径。D(1)ij=minD(0)ij,D(0)i1+D(0)1j0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888A(-1)=47D(0)=1036D(1)=V0V1V0V1第5页/共16页V2V3V0V112345689 以D(1)为基础，以V2为中间顶点，求从Vi,到Vj的最短路径。

5、或者为从Vi到Vj的边,或者为从Vi开始通过V0,V1,V2到达Vj的最短路径。D(2)ij=minD(1)ij,D(1)i2+D(1)2j0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888A(-1)=47A(0)=1036D(1)=D(2)=12 910V0V1V2第6页/共16页0 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888A(-1)=47A(0)=1036A(1)=D(2)=12 910D(3)=V2V3V0V112345689 以D(2)为基础，以V3为中间顶点，求从Vi,到Vj的最短路

6、径。或者为从Vi到Vj的边,或者为从Vi开始通过V0,V1,V2,V3到达Vj的最短路径。D(3)ij=minD(2)ij,D(2)i3+D(2)3j 9 11 8V3V2V0V1 D(3)ij 即为从Vi到Vj的最短路径长度.第7页/共16页8ACB2643110 4 116 0 23 0初始：初始：路径：路径：AB ACBA BCCA0 4 66 0 23 7 0加入加入B：路径：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入加入A：路径：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入加入C：路径：路径：AB ABCBCA BCCA

7、CAB例题：第8页/共16页9例例ACB264311初始：初始：0 4 116 0 23 0length=0 1 12 0 23 0 0path=加入加入A：0 4 116 0 23 7 0length=0 1 12 0 23 1 0path=加入加入B：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入加入C：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=第9页/共16页10 4.4.4.4.论点：论点：A A(-1)(-1)i ij j 是从顶点是从顶点v vi i 到到v vj j,中间顶点是中间顶点是 v v1

8、 1的最短路径的长度的最短路径的长度,A A(k k)i ij j 是从顶点是从顶点v vi i 到到v vj j,中间顶点的序号不大于中间顶点的序号不大于k k的最短路径的长度的最短路径的长度,A A(n-1n-1)i ij j 是从顶点是从顶点v vi i 到到v vj j 的最短路径长度。的最短路径长度。证明：证明：归纳证明，始归纳于归纳证明，始归纳于s(s(上角标上角标););(1)(1)归纳基础：当归纳基础：当s=-1 s=-1 时，时，A A(-1)(-1)i ij j=EdgeEdge i ij j,v vi i 到到v vj j,不经过任何顶点不经过任何顶点的边，是最短路径。的

9、边，是最短路径。(2)(2)归纳假设：当归纳假设：当sksk时，时，A A(s)(s)i ij j 是从顶点是从顶点v vi i 到到v vj j,中间顶点的序号不大于中间顶点的序号不大于s s的的最短路径的长度最短路径的长度;(3)(3)当当s=ks=k时，时，第10页/共16页11 ijkA(k-1)ikA(k-1)kjA(k-1)ij因为：因为：因为：因为：A A A A(k k k k)i i i ij j j j=min =min =min =min A A A A(k k k k-1)-1)-1)-1)i i i ij j j j ，A A A A(k k k k-1)-1)-1)

10、-1)i i i ik k k k+A A A A(k k k k-1)-1)-1)-1)k k k kj j j j 由归纳假设知：由归纳假设知：由归纳假设知：由归纳假设知：A A A A(k k k k-1)-1)-1)-1)i i i ij j j j:是是是是i i i i到到到到j j j j的最短路径的最短路径的最短路径的最短路径(标号不高于标号不高于标号不高于标号不高于k-1)k-1)k-1)k-1)；A A A A(k k k k-1)-1)-1)-1)i i i ik k k k:是是是是i i i i到到到到k k k k的最短路径的最短路径的最短路径的最短路径(标号不高于

11、标号不高于标号不高于标号不高于k-1)k-1)k-1)k-1)；A A A A(k k k k-1)-1)-1)-1)k k k kj j j j:是是是是k k k k到到到到j j j j的最短路径的最短路径的最短路径的最短路径(标号不高于标号不高于标号不高于标号不高于k-1)k-1)k-1)k-1)；所以：所以：所以：所以：A A A A(k k k k)i i i ij j j j 是是是是i i i i到到到到j j j j的最短路径的最短路径的最短路径的最短路径(标号不高于标号不高于标号不高于标号不高于k)k)k)k)。第11页/共16页12图用邻接矩阵存储edge 存放最短路径长

12、度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;/缩短路径缩短路径,绕过绕过

13、 k 到到 j /floyd 第12页/共16页136.6.算法分析：算法分析：设最内层循环体为基本操作，算法有三层循环，设最内层循环体为基本操作，算法有三层循环，每层循环每层循环n n次，所以次，所以T(n)=O(nT(n)=O(n3 3)第13页/共16页14第14页/共16页15 以以以以 PathPath(3)(3)为例，对最短路径的读法加以说明。为例，对最短路径的读法加以说明。为例，对最短路径的读法加以说明。为例，对最短路径的读法加以说明。从从从从A A(3)(3)知，顶点知，顶点知，顶点知，顶点1 1到到到到0 0的最短路径长度的最短路径长度的最短路径长度的最短路径长度为为为为a a10=11,10=11,其最短路径看其最短路径看其最短路径看其最短路径看 pathpath110 0=2 2，pathpath112 2=3 3，path path 113 3=1 1,表示顶点表示顶点表示顶点表示顶点0 0 顶点顶点顶点顶点2 2 顶点顶点顶点顶点3 3 顶点顶点顶点顶点1;1;从顶点从顶点从顶点从顶点1 1到顶点到顶点到顶点到顶点0 0最短路径为最短路径为最短路径为最短路径为,。第15页/共16页感谢您的观看！第16页/共16页