最短路径算法--Floyd算法.ppt

《最短路径算法--Floyd算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Floyd’sAlgorithmAllpairsshortestpath1AllpairsshortestpathTheproblem:findtheshortestpathbetweeneverypairofverticesofagraphThegraph:maycontainnegativeedgesbutnonegativecyclesArepresentation:aweightmatrixwhereW(i,j)=0ifi=j.W(i,j)=¥ifthereisnoedgebetweeniandj.W(i

2、,j)=“weightofedge”Note:wehaveshownprincipleofoptimalityappliestoshortestpathproblems2Theweightmatrixandthegraphv1v2v3v4v532241319353ThesubproblemsHowcanwedefinetheshortestdistancedi,jintermsof“smaller”problems?Onewayistorestrictthepathstoonlyincludeverticesfroma

3、restrictedsubset.Initially,thesubsetisempty.Then,itisincrementallyincreaseduntilitincludesallthevertices.4ThesubproblemsLetD(k)[i,j]=weightofashortestpathfromvitovjusingonlyverticesfrom{v1,v2,…,vk}asintermediateverticesinthepathD(0)=WD(n)=DwhichisthegoalmatrixHo

4、wdowecomputeD(k)fromD(k-1)?5TheRecursiveDefinition:Case1:Ashortestpathfromvitovjrestrictedtousingonlyverticesfrom{v1,v2,…,vk}asintermediateverticesdoesnotusevk.ThenD(k)[i,j]=D(k-1)[i,j].Case2:Ashortestpathfromvitovjrestrictedtousingonlyverticesfrom{v1,v2,…,vk}as

5、intermediateverticesdoesusevk.ThenD(k)[i,j]=D(k-1)[i,k]+D(k-1)[k,j].ViVjVkShortestPathusingintermediatevertices{V1,...Vk-1}Shortestpathusingintermediatevertices{V1,...Vk}6TherecursivedefinitionSinceD(k)[i,j]=D(k-1)[i,j]orD(k)[i,j]=D(k-1)[i,k]+D(k-1)[k,j].Wecon

6、clude:D(k)[i,j]=min{D(k-1)[i,j],D(k-1)[i,k]+D(k-1)[k,j]}.ViVjVkShortestPathusingintermediatevertices{V1,...Vk-1}Shortestpathusingintermediatevertices{V1,...Vk}7ThepointerarrayPUsedtoenablefindingashortestpathInitiallythearraycontains0Eachtimethatashorterpathfro

7、mitojisfoundthekthatprovidedtheminimumissaved(highestindexnodeonthepathfromitoj)Toprinttheintermediatenodesontheshortestpatharecursiveprocedurethatprinttheshortestpathsfromiandk,andfromktojcanbeused8Floyd'sAlgorithmUsingn+1DmatricesFloyd//Computesshortestdistanc

8、ebetweenallpairsof//nodes,andsavesPtoenablefindingshortestpaths1.D0W//initializeDarraytoW[]2.P0//initializeParrayto[0]3.fork1ton4.dofori1ton5.doforj1ton6.if(Dk-1