資源描述：
《最短路徑算法--Floyd算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、Floyd’sAlgorithmAllpairsshortestpath1AllpairsshortestpathTheproblem:findtheshortestpathbetweeneverypairofverticesofagraphThegraph:maycontainnegativeedgesbutnonegativecyclesArepresentation:aweightmatrixwhere W(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
