GraphTheoryChapter4PathsandDistanceinGraphs大葉大學資訊工程系:puter:AmessagemustbesentfromaprocessorP1toaprocessorP2intheminimumpossible?10processors兩點連線表示彼此可溝通每條邊所需的溝通時間相同FindshortestP1-:ForanontrivialgraphGandapairu,vofverticesofG,thedistancedG(u,v)(ord(u,v)ifthegraphGisclearfromcontext)betweenuandvisthelengthofashortestu--vpath,thenwedefined(u,v)=∞.G1:vuG2:yxd(x,y)=∞d(u,v)=24Definition:ThedistancefunctiononagraphGisametric,thatis,itmapsV(G)V(G)tothesetofnonnegativeintegersandsatisfiesthefollowingfundamentalproperties:(接下頁):(i)d(u,v)0,andd(u,v)=0iffu=v;(ii)d(u,v)=d(v,u)forallu,vV(G);(iii)d(u,v)d(u,w)+d(w,v)forallu,v,wV(G)(thetriangleinequality).Pf:[(i)and(ii),seeproblem1.](iii),weproceedasfollows:Letu,v,–wpathandQashortestw––vwalk,sayW,havinglengthd(u,w)+d(w,v).SinceWcontainsau–vpath(),itfollowsthatd(u,v)d(u,w)+d(w,v).6Definition:ForadirectedgraphD,the(directed)distancedD(u,v)(ord(u,v))fromvertexutovertexvofDisthelengthofashortestdirectedu-vpathifsuchapathexists,andis∞:zwxvuyd(u,v)=∞d(u,z)=(Moore’sBreadth-FirstSearchAlgorithm)Foreveryvertexwu,letl(w)←∞.Further,letl(u)←,thendeleteavertexxfromQ;otherwise,stop,sincethereisnou-(y)=∞,assignPARENT(y)←x,letl(y)←l(x)+(v)=∞,thenreturnStep2;otherwise,←l(v)anduk←0,thenuk-1←PARENT(uk);←k-,u1,…,uk,whichisashortestu–vpath.(Forgivenuv,findd(u,v)andashortestu-vpath.)l(v)即是d(u,v)u,letl(u)←.Further,letl(u)←,=,thenoutputthepairsv,l(v)forallve
大叶大学 来自淘豆网www.taodocs.com转载请标明出处.