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

11.问题的提出：已知一个各边权值均大于0的带权有向图，对每一对顶点vivj，要求求出vi与vj之间的最短路径和最短路径长度。2.解决办法方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次——T(n)=O(n³)方法二：弗洛伊德(Floyd)算法2–求最短路径步骤•初始时设置一个n阶方阵，令其对角线元素为0，若存在弧Vi,Vj，则对应元素为权值；否则为•逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值•所有顶点试探完毕，算法结束3.Floyd算法思想：逐个顶点试探法从图的带权邻接矩阵G.arcs出发，假设求顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为G.arcs[i][j]的路径，但该路径是否一定是最短路径，还需要进行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，继续进行试探。V2V3V0V1123456890123012301240092350801608888D(-1)=D(-1)为有向网的邻接矩阵第一步:以D(-1)为基础，以V0为中间顶点，求从Vi到Vj的最短路径。该路径或者为从Vi到Vj的边,或者为(Vi,V0)+(V0,Vj)。D(0)[i][j]=min{D(-1)[i][j],D(-1)[i][0]+D(-1)[0][j]}47D(0)=D(0)[i][j]为从Vi到Vj的中间顶点序号不大于0的最短路径长度.V0V2V3V0V112345689以D(0)为基础，以V1为中间顶点，求从Vi,到Vj的最短路径。该路径或者为从Vi到Vj的边,或者为从Vi开始通过V0或V1到达Vj的最短路径。D(1)[i][j]=min{D(0)[i][j],D(0)[i][1]+D(0)[1][j]}0123012301240092350801608888A(-1)=47D(0)=1036D(1)=V0V1V0V1V2V3V0V112345689以D(1)为基础，以V2为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边,或者为从Vi开始通过V0,V1,V2到达Vj的最短路径。D(2)[i][j]=min{D(1)[i][j],D(1)[i][2]+D(1)[2][j]}0123012301240092350801608888A(-1)=47A(0)=1036D(1)=D(2)=12910V0V1V20123012301240092350801608888A(-1)=47A(0)=1036A(1)=D(2)=12910D(3)=V2V3V0V112345689以D(2)为基础，以V3为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边,或者为从Vi开始通过V0,V1,V2,V3到达Vj的最短路径。D(3)[i][j]=min{D(2)[i][j],D(2)[i][3]+D(2)[3][j]}9118V3V2V0V1D(3)[i][j]即为从Vi到Vj的最短路径长度.9ACB264311041160230初始：路径：ABACBABCCA046602370加入B：路径：ABABCBABCCACAB0411602370加入A：路径：ABACBABCCACAB046502370加入C：路径：ABABCBCABCCACAB例题：10例ACB264311初始：041160230length=011202300path=加入A：0411602370length=011202310path=加入B：046602370length=012202310path=加入C：046502370length=012302310path=114.论点：A(-1)[i][j]是从顶点vi到vj,中间顶点是v1的最短路径的长度,A(k)[i][j]是从顶点vi到vj,中间顶点的序号不大于k的最短路径的长度,A(n-1)[i][j]是从顶点vi到vj的最短路径长度。证明：归纳证明，始归纳于s(上角标);(1)归纳基础：当s=-1时，A(-1)[i][j]=Edge[i][j],vi到vj,不经过任何顶点的边，是最短路径。(2)归纳假设：当sk时，A(s)[i][j]是从顶点vi到vj,中间顶点的序号不大于s的最短路径的长度;(3)当s=k时，12ijkA(k-1)[i][k]A(k-1)[k][j]A(k-1)[i][j]因为：A(k)[i][j]=min{A(k-1)[i][j]，A(k-1)[i][k]+A(k-1)[k][j]}由归纳假设知：A(k-1)[i][j]:是i到j的最短路径(标号不高于k-1)；A(k-1)[i][k]:是i到k的最短路径(标号不高于k-1)；A(k-1)[k][j]:是k到j的最短路径(标号不高于k-1)；所以：A(k)[i][j]是i到j的最短路径(标号不高于k)。13•图用邻接矩阵存储•edge[][]存放最短路径长度•path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号5.算法实现voidfloyd(){for(inti=0;in;i++)//矩阵dist与path初始化for(intj=0;jn;j++){//置A(-1)dist[i][j]=Edge[i][j];path[i][j]=-1;}//初始不经过任何顶点for(intk=0;kn;k++)//产生dist(k)及path(k)for(i=0;in;i++)for(j=0;jn;j++)if(dist[i][k]+dist[k][j]dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=k;}//缩短路径,绕过k到j}//floyd146.算法分析：设最内层循环体为基本操作，算法有三层循环，每层循环n次，所以T(n)=O(n3)15A(-1)A(0)A(1)A(2)A(3)012301230123012301230014014011030110301931092092092120921108223508340734063406340636060609106091060Path(-1)Path(0)Path(1)Path(2)Path(3)0123012301230123012300000000000110011003110011001100112011203122202200020012001200130030003000302030203016A(-1)A(0)A(1)A(2)A(3)012301230123012301230014014011030110301931092092092120921108223508340734063406340636060609106091060Path(-1)Path(0)Path(1)Path(2)Path(3)01230123012301230123000000000001100110031100110011001120112031222022000200120012001300300030003020302030以Path(3)为例，对最短路径的读法加以说明。从A(3)知，顶点1到0的最短路径长度为a[1][0]=11,其最短路径看path[1][0]=2，path[1][2]=3，path[1][3]=1,表示顶点0顶点2顶点3顶点1;从顶点1到顶点0最短路径为1,3,3,2,2,0。