1、12.解决办法解决办法方法一方法一:每次以一个顶点为源点,重复执行:每次以一个顶点为源点,重复执行Dijkstra算法算法n次次 T(n)=O(n)方法二方法二:弗洛伊德:弗洛伊德(Floyd)算法算法2求最短路径步骤求最短路径步骤初始时设置一个初始时设置一个n n阶方阵,令其对角线元素为阶方阵,令其对角线元素为0 0,若存在弧,若存在弧 Vi,Vj,则对应元素为权值;否则则对应元素为权值;否则为为 逐步试着在原直接路径中增加中间顶点,若加逐步试着在原直接路径中增加中间顶点,若加入中间点后路径变短,则修改之;否则,维持入中间点后路径变短,则修改之;否则,维持原值原值所有顶点试探完毕,算法结束所
2、有顶点试探完毕,算法结束3.Floyd算法思想:逐个顶点试探法算法思想:逐个顶点试探法 从图的带权邻接矩阵从图的带权邻接矩阵G.arcsG.arcs出发,假设求顶点出发,假设求顶点ViVi到到VjVj的最短路径。如果从的最短路径。如果从ViVi到到VjVj有弧,则从有弧,则从ViVi到到VjVj存在一条长度为存在一条长度为G.arcsijG.arcsij的路径,但该路的路径,但该路径是否一定是最短路径,还需要进行径是否一定是最短路径,还需要进行n n次试探。次试探。1.第一次,判别(Vi,V0)和(V0,Vj ),即判别(Vi,V0,Vj)是否存在,若存在,则比较(Vi,Vj)和(Vi,V0,
3、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,继续进行试探。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)为有向网的邻接矩
4、阵 第一步:以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 为从Vi到Vj的的最短路径长度.V0V2V3V0V112345689 以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
5、 8888A(-1)=47D(0)=1036D(1)=V0V1V0V1V2V3V0V112345689 以D(1)为基础,以V2为中间顶点,求从Vi,到Vj的最短路径。或者为从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 910V0V1V20 1 2 3 0123 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8888A(-1)=47A
6、(0)=1036A(1)=D(2)=12 910D(3)=V2V3V0V112345689 以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 9 11 8V3V2V0V1 D(3)ij 即为从Vi到Vj的最短路径长度.9ACB2643110 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加入
7、加入A:路径:路径:AB ACBA BCCA CAB0 4 65 0 23 7 0加入加入C:路径:路径:AB ABCBCA BCCA CAB例题:例题:10例例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=11论点:论点:A A(-1)(-1
8、)i ij j 是从顶点是从顶点v vi i 到到v vj j,中间顶点是中间顶点是 v v1 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
9、i ij j,v vi i 到到v vj j,不经过任何顶点的边,是最短路径。不经过任何顶点的边,是最短路径。(2)(2)归纳假设:当归纳假设:当sksk时,时,A A(s)(s)i ij j 是从顶点是从顶点v vi i 到到v vj j,中间顶点的序号不大于中间顶点的序号不大于s s的最短路径的长度的最短路径的长度;(3)(3)当当s=ks=k时,时,12ijkA(k-1)ikA(k-1)kjA(k-1)ij13 图用邻接矩阵存储图用邻接矩阵存储 edge 存放最短路径长度存放最短路径长度 pathij是从是从Vi到到Vj的最短路径上的最短路径上Vj前一顶点序号前一顶点序号5.算法实现算法
10、实现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 146.6.算法分析:算法分析:设最内层循
11、环体为基本操作,算法有三层循环,设最内层循环体为基本操作,算法有三层循环,每层循环每层循环n n次,所以次,所以T(n)=O(nT(n)=O(n3 3)15 A(-1)A(0)A(1)A(2)A(3)0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0 1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1)
12、Path(0)Path(1)Path(2)Path(3)0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 2 0 1 1 2 0 3 1 2 2 2 0 2 2 0 0 0 2 0 0 1 2 0 0 1 2 0 0 1 3 0 0 3 0 0 0 3 0 0 0 3 0 2 0 3 0 2 0 3 0结束语当你尽了自己的最大努力时,失败也是伟大的,所以不要放弃,坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings演讲人:XXXXXX 时 间:XX年XX月XX日