最短路径算法--Floyd算法

Floyd’sAlgorithm1Floyd’sAlgorithmAllpairsshortestpathFloyd’sAlgorithm2Allpairsshortestpath•Theproblem:findtheshortestpathbetweeneverypairofverticesofagraph•Thegraph:maycontainnegativeedgesbutnonegativecycles•Arepresentation:aweightmatrixwhereW(i,j)=0ifi=j.W(i,j)=ifthereisnoedgebetweeniandj.W(i,j)=“weightofedge”•Note:wehaveshownprincipleofoptimalityappliestoshortestpathproblemsFloyd’sAlgorithm3Theweightmatrixandthegraph1234510115290323044203530v1v2v3v4v53224131935Floyd’sAlgorithm4Thesubproblems•Howcanwedefinetheshortestdistancedi,jintermsof“smaller”problems?•Onewayistorestrictthepathstoonlyincludeverticesfromarestrictedsubset.•Initially,thesubsetisempty.•Then,itisincrementallyincreaseduntilitincludesallthevertices.Floyd’sAlgorithm5Thesubproblems•LetD(k)[i,j]=weightofashortestpathfromvitovjusingonlyverticesfrom{v1,v2,…,vk}asintermediateverticesinthepath–D(0)=W–D(n)=Dwhichisthegoalmatrix•HowdowecomputeD(k)fromD(k-1)?Floyd’sAlgorithm6TheRecursiveDefinition:Case1:Ashortestpathfromvitovjrestrictedtousingonlyverticesfrom{v1,v2,…,vk}asintermediateverticesdoesnotusevk.ThenD(k)[i,j]=D(k-1)[i,j].Case2:Ashortestpathfromvitovjrestrictedtousingonlyverticesfrom{v1,v2,…,vk}asintermediateverticesdoesusevk.ThenD(k)[i,j]=D(k-1)[i,k]+D(k-1)[k,j].ViVjVkShortestPathusingintermediatevertices{V1,...Vk-1}Shortestpathusingintermediatevertices{V1,...Vk}Floyd’sAlgorithm7Therecursivedefinition•SinceD(k)[i,j]=D(k-1)[i,j]orD(k)[i,j]=D(k-1)[i,k]+D(k-1)[k,j].Weconclude: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}Floyd’sAlgorithm8ThepointerarrayP•Usedtoenablefindingashortestpath•Initiallythearraycontains0•Eachtimethatashorterpathfromitojisfoundthekthatprovidedtheminimumissaved(highestindexnodeonthepathfromitoj)•Toprinttheintermediatenodesontheshortestpatharecursiveprocedurethatprinttheshortestpathsfromiandk,andfromktojcanbeusedFloyd’sAlgorithm9Floyd'sAlgorithmUsingn+1DmatricesFloyd//Computesshortestdistancebetweenallpairsof//nodes,andsavesPtoenablefindingshortestpaths1.D0W//initializeDarraytoW[]2.P0//initializeParrayto[0]3.fork1ton4.dofori1ton5.doforj1ton6.if(Dk-1[i,j]Dk-1[i,k]+Dk-1[k,j])7.thenDk[i,j]Dk-1[i,k]+Dk-1[k,j]8.P[i,j]k;9.elseDk[i,j]Dk-1[i,j]Floyd’sAlgorithm10ExampleW=D0=40520-30123123000000000123123P=1235-324Floyd’sAlgorithm11D1=405207-30123123000001000123123P=1235-324k=1Vertex1canbeintermediatenodeD1[2,3]=min(D0[2,3],D0[2,1]+D0[1,3])=min(,7)=7D1[3,2]=min(D0[3,2],D0[3,1]+D0[1,2])=min(-3,)=-340520-30123123D0=Floyd’sAlgorithm12D2=405207-1-30123123000001200123123P=D2[1,3]=min(D1[1,3],D1[1,2]+D1[2,3])=min(5,4+7)=5D2[3,1]=min(D1[3,1],D1[3,2]+D1[2,1])=min(,-3+2)=-11235-324D1=405207-30123123k=2Vertices1,2canbeintermediateFloyd’sAlgorithm13D3=205207-1-30123123300001200123123P=D3[1,2]=min(D2[1,2],D2[1,3]+D2[3,2])=min(4,5+(-3))=2D3[2,1]=min(D2[2,1],D2[2,3]+D2[3,1])=min(2,7+(-1))=2D2=405207-1-301231231235-324k=3Vertices1,2,3canbeintermediateFloyd’sAlgorithm14Floyd'sAlgorithm:Using2DmatricesFloyd1.DW//initializeDarraytoW[]2.P0//initializeParrayto[0]3.fork1ton//ComputingD’fromD4.dofori1ton5.doforj1ton6.if(D[i,j]D[i,k]+D[k,j])7.thenD’[i,j]D[i,k]+D[k,j]8.P[i,j]k;9.elseD’[i,j]D[i,j]10.MoveD’toD.Floyd’sAlgorithm15CanweuseonlyoneDmatrix?•D[i,j]dependsonlyonelementsinthekthcolumnandrowofthedistancematrix.•WewillshowthatthekthrowandthekthcolumnofthedistancematrixareunchangedwhenDkiscomputed•ThismeansDcanbecalculatedin-placeFloyd’sAlgorithm16Themaindiagonalvalues•BeforeweshowthatkthrowandcolumnofDremainunchangedweshowthatthemaindiagonalremains0•D(k)[j,j]=min{D(k-1)[j,j],D(k-1)[j,k]+D(k-1)[k,j]}=min{0,D(k-1)[j,k]+D(k-1)[k,j]}=0•Basedonwhichassumption?Floyd’sAlgorithm17Thekthcolumn•kthcolumnofDkisequaltothekthcolumnofDk-1•Intuitivelytrue-apathfromitokwillnotbecomeshorterbyaddingktotheallowedsubsetofintermediatevertices•Foralli,D(k)[i,k]==min{D(k-1)[i,k],D(k-1)[i,k]+D(k-1)[k,k]}=min{D(k-1)[i,k],D(k-1)[i,k]+0}=D(k-1)[i,k]Floyd’sAlgorithm18Thekthrow•kthrowofDkisequaltothekthrowofDk-1Forallj,D(k)[k,j]==min{D(k-1)[k,j],D(k-1)[k,k]+D(k-1)[k,j]}=min{D(k-1)[k,j],0+D(k-1)[k,j]}=D(k-1)[k,j]Floyd’sAlgorithm19Floyd'sAlgorithmusingasingleDFloyd1.DW//initializeDarraytoW[]2.P0//initializeParrayto[0]3.fork1ton4.dofori1ton5.doforj1ton6.if(D[i,j]D[i,k]+D[k,j])7.thenD[i,j]D[i,k]+D[k,j]8.P[i,j]k;Floyd’sAlgorithm20Printingintermediatenodesonshortestpathfromqtorpath(indexq,r)if(P[q,r]!=0)path(q,P[q,r])println(“v”+P[q,r])path(P[q,r],r)return;//nointermediatenodeselsereturnBeforecallingpathcheckD[q,r],andprintnodeq,afterthecalltopathprintnoder300001200123123P=1235-324Floyd’sAlgorithm21ExampleFloyd’sAlgorithm22ThevaluesinparenthesisarethenonzeroPvalues.ThefinaldistancematrixandPFloyd’sAlgorithm23Path(1,4)Path(1,6)Path(6,4)Printv6Path(6,3)Printv3Path(3,4)P(1,6)=0P(6,3)=0P(3,4)=0Theintermediatenodesontheshortestpathfrom1to4arev6,v3.Theshortestpathisv1,v6,v3,v4.ThecalltreeforPath(1,4)