算法最短路径弗洛伊德算法.ppt

算法最短路径弗洛伊德算法*求最短路径步骤初始时设置一个n阶方阵,令其对角线元素为0,若存在弧<Vi,Vj>,则对应元素为权值;否则为逐步试着在原直接路径中增加中间顶点,若加入中间点后路径变短,则修改之;否则,维持原值所有顶点试探完毕,:,假设求顶点Vi到Vj的最短路径。如果从Vi到Vj有弧,[i][j]的路径,但该路径是否一定是最短路径,还需要进行n次试探。,判别(Vi,V0)和(V0,Vj),即判别(Vi,V0,Vj)是否存在,若存在,则比较(Vi,Vj)和(Vi,V0,Vj)的长度,取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。,再加一个顶点V1,如果(Vi,…,V1)和(V1,…,Vj)分别是当前找到的中间顶点序号不大于0的最短路径,那么(Vi,…,V1,…,Vj)就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较,取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径。,再加一个顶点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](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的最短路径长度.*ACB264311041160230初始:路径:A046602370加入B:路径:ACAB0411602370加入A:路径:ACAB046502370加入C:路径:ACAB例题:*例ACB264311初始:041160230length=011202300path=加入A:0411602370length=011202310path=加入B:046602370length=012202310path=加入C:046502370length=012302310path=