最短路径文献翻译终极版

单位代码学号分类号O24密级文献翻译最短通路问题UJ最短通路问题UJ院（系）名称信息工程学院专业名称信息与计算科学学生姓名许秀成指导教师孙贵玲8.6最短通路问题8.6.1引言许多问题可以用边上赋权的图来建模。考虑一下航线系统如何建模。如果用顶点表示城市，用边表示航线。给边赋上城市之间的距离，就可以为涉及距离的问题建模；给边赋上飞行时间，就可以为涉及飞行时间的问题建模；给边赋上票价，就可以为涉及票价的问题建模。图8—61显示了给一个图的边赋权的三种不同方式，分别表示距离，飞行时间和票价。

给每条边赋上一个数的图称为带权图。带权图用来为计算机网络建模。通信成本（比如租用电话线的月租费）、计算机在这些线路上的响应时间或是计算机之间的距离等都可以用带权图来研究。图8—62显示一些带权图，它们表示给计算机的图的边赋权的三种方式，分别对应成本、响应时间和距离。与带权图有关的几种类型的问题出现得很多。确定网络里两个顶点之间长度最短的通路就是一个这样的问题。说的更具体些，设带权图里一条通路的长度是这条通路上各边的权的总和。（读者应当注意，对术语长度的这种用法，与表示不带权的图的通路里边数的长度的用法，这两者是不同的。）问题是：什么是最短通路，即什么是在两个给定顶点之间长度最短的通路?例如，在图8—61所示带权图表示的航线系统里，在波士顿与洛杉矶之间以空中距离计算的最短通路是什么？在波士顿与洛杉矶之间什么样的航班组合的总飞行时间（即在空中的总时间，不包括航班之间的时间）最短？在这两个城市之间的最低费用是多少？

图8-62为计算机网络建模的带权图在图8—62所示的计算机网络里，连接旧金山的计算机与纽约的计算机所需要的最便宜的一组电话线是什么？哪一组电话线给出旧金山与纽约之间的通信的最短响应时间？哪一组电话线有最短的总距离？与带权图有关的另外的一个重要问题是：求访问完全图每个顶点恰好一次的、总长度最短的回路。这就是著名的旅行商问题，它求一位推销商应当以什么样的顺序来访问其路程上的每个城市恰好一次，使得他旅行的总距离最短。本节后面将讨论旅行商问题。8.6.2最短通路算法求带权图里两个顶点之间的最短通路有几个不同的算法。下面将给出荷兰数学家E•迪克斯特拉在1959年所发现的一个解决无向带权图中最短通路问题的算法，其中所有的权都是正数。可以很容易地将它修改后来解决有向图里的最短通路问题。在给出这个算法的形式化表示之前将给出一个启发性的例子。例1在图8-63所示的带权图里，a和乙之间的最短通路的长度是多少?解虽然通过观察就容易求出最短通路，但是需要想出一些有助于理解迪克施特拉算法的办法。要解决的问题就是：求从a到各个相继的顶点的最短通路，直到到达z为止。从a开始、（直到到达终点为止）不包括除a以外的顶点的唯一通路是a,b和a,d。因为a,b和a,d的长度分别是4和2,所以d是与a最近的顶点。可以通过查看（直到到达终点为止）只经过a和d的所有通路，来求出下一个最靠近a的顶点。到b的最短通路仍然是a，b，长度为4,而到e的最短通路是a,d,e，长度为5。所以，下一个与a最靠近的顶点是b。为了找出第三个与a最近的顶点，只需要检查（直到到达终点为止）只经过了a,d和b的那些通路。存在长度为7到c的通路，即a,b,c,以及长度为6到z的通路，即a,d,e,z。所以，z是下一个与a最靠近的顶点，而且到z的最短通路的长度为6。例1说明了在迪克斯特拉算法里使用的一般原理。注意通过检查就可能求出从a到z最短通路。不过，无论对人还是对计算机来说，检查边数很多的图都是不切实际的。现在将考虑一般问题：在无向联通简单带权图里，求出a与z之间的最短通路的长度。迪克斯特拉算法如下进行：求出从a到第一个顶点的最短通路的长度，从a到第二个顶点最短通路的长度，以此类推，直到求出a到z的最短通路长度为止。这个算法依赖于一系列的迭代。通过在每次跌代里添加一个顶点来构造出特殊顶点的集合。在每次跌代里完成一个标记过程。在这个标记过程，只包括特殊顶点的从a到"的最短通路的长度来标记w。添加到特殊顶点集里的顶点是尚在集合之外的那些顶点中带有最小标记的顶点。现在给出迪克斯特拉算法的细节。它首先用0标记^而用8标记其余的顶点。用记号L0（a）=0和L0（v）=8表示在没有发生任何迭代之前的这些标记（下标0表示“第0次”迭代）。这些标记是从a到这些顶点的最短通路的长度，其中这些通路只包含顶点a。（因为不存在a到其他顶点的这种通路，所以8是a与这样的顶点之间的最短通路的长度。）迪克斯特拉算法是通过形成特殊顶点的集合来进行的。设Sk表示在标记过程k次迭代之后的特殊顶点集。首先s0m。集合sk是通过过程把不属于%_1的带最小标记的顶点u添加到Sk_1里形成的，一旦把u添加到七里，就更新所有不属于Sk的顶点的标记，使得顶点v在第个阶段的标记匕（v）是只包含Sk里顶点（即已有的特殊点再加上u）的、从a到v的最短通路的长度。设v是不属于S的一个顶点。为了更新v的标记，注意Lk（v）是只包含七里k顶点的从a到v的最短通路，要么是只包含Sk_］里顶点（即不包括u在内的特殊顶点）的从a到v的最短通路，要么k-1阶段加上边（u,v）的从a到u的最短通路。换句话说，L(a,v)=min{l(a,v)L(a,u)+w(u,v)}这个过程这样迭代：相继添加顶点到特殊顶点集里，直到添加z为止。当把z添加到特殊顶点集里时，它的标记就是从a到z的最短通路的长度。在算法1里给出迪克斯特拉算法。随后将证明这个算法的正确性。算法1迪克施特拉算法ProcedureDijkkstra（G:所有权都为正数的带权连通简单图）{G带有顶点a=vv,...=z和权w(vv)，其中若{v,v}不是G里的边，则w(vv)=s}0,1i,jiji,jFori:=1tonL(v):=siL(a):=0(现在初始化标记，使得^的标记为0而所有其余标记为US是空集合｝Whilez史SBeginu:=不属于S的L(u)最小的一个顶点S:=S｛u｝For所有不属于S的顶点vIfL(u)+w(u,v)<L(v)thenL(v):=L(u)+w(u,v)｛这样就给S里添加带最小标记的顶点，而且更新不在S里的顶点的标记｝end｛L(z)=从a到z的最短通路的长度｝下面的例子说明迪克施特拉算法是如何工作的。随后我们将证明这个算法总是产生带权图里两个顶点之间最短通路的长度。例2用迪克施特拉算法求图8—64a所示的带权图里顶点a与z之间最短通路的长度。解图8—64里显示了迪克斯特拉算法求a与z之间最短通路所用的步骤。在算法的每次迭代里，用圆圈圈起集合S*里的顶点。对每次迭代都标明了只包含S*里顶点的从a到每个顶点的最短通路。当圆圈圈到z时，算法终止。找到从a到z的最短通路是a,c,b,d,e,长度为13。下一步，用归纳论证来证明迪克斯特拉算法产生无向连通带权图里两个顶点a与z之间最短通路的长度。用下列断言作为归纳假设:在第k次迭代里⑴S里的顶点v(v主0)的标记是从a到这个顶点的最短通路的长度。(ii)不在S里的顶点的标记是(这个顶点自身除外)只包含S里顶点的最短通路的长度。当k=0时，在没有执行任何迭代之前，S=｛a｝，所以从a到除a外的顶点的最短通路长度是8。设v是第k+1次迭代里添加到S里的顶点，使得v是在第k次迭代结束时带最小标记的不在S里的顶点不唯一的情形里，可以采用带最小标记的任意顶点。根据归纳假设，可以看出在第k+1次迭代之前，S里的顶点都用从a出发的最短通

图8-64用迪克斯特拉算法求从a至Ijz的最短距离另外，必须用从a到v的最短通路的长度来标记v。假如情况不是这样，那么在第化次迭代结束时，就可能存在包含不在S里的顶点的、长度小于匕(v)的通路(因为匕(v)是在第k次迭代之后、只包含S里顶点的、从a到v的最短通路的长度)。设u是在这样的通路里不属于S的第一个顶点。则存在一条只包含S里顶点的、从a到u的长度小于L(v)的通路。这与对v的选择相矛盾。因此，在第k+1次迭代时⑴成立。设u是在第k+1次迭代之后不属于S的一个顶点。只包含S里顶点的从a到u的最短通路要么包含v、要么不包含v。若它不包含v，则根据归纳假设，它的长度是匕(u)。若它确实包含v，则它必然是这样组成的：一条只包含S里除v之外的顶点的、从a到v具有最短可能长度的通路，后面接着从v到u的边。这种情形里它的长度是L(v)+w(v,u)。这样就证明了(ii)为真，因为L(u)=min{LL+w(v,u)}。kk+1k(u),k(v)已经证明了定理1.定理1迪克斯特拉算法求出连通简单无向带权图里两个顶点之间最短通路的长度。现在可以估计迪克斯特拉算法的计算复杂性(就加法和比较而言)。这个算法使用的迭代次数不超过n-1次，因为在每次迭代里添加一个顶点到特殊顶点集里。若可以估计每次迭代所使用的运算次数，则大功告成。可以用不超过n-1次比较来找出不在Sk里的带最小标记的顶点。于是我们使用一次加法和一次比较来更新不在S中的每一个顶点k的标记，所以在每次迭代里的运算不超过2(n-1)次，因为在每次迭代里要更新的标记不超过n-1个。因为迭代次数不超过n-1次，每次迭代的运算次数不超过2(n-1)，所以有下面的定理。定理2迪克斯特拉算法使用0(n2)次运算(加法和比较)来求出连通简单无向带权图里两个顶点之间最短通路的长度。来源于：罗森(美).离散数学及其应用.北京：机械工业出版社，2003.8(6)：491-496.附:英文原文8.6Shortest-PathProblems8.6.1IntroductionManyproblemscanbemodeledusinggraphswithweightsassignedtotheiredges.Asanillustration,considerhowanairlinesystemcanbemodeled.Wesetupthebasicgraphmodelbyrepresentingcitiesbyverticesandflightsbyedges.Problemsinvolvingflighttimecanbemodeledbyassigningflighttimestoedges.Problemsinvolvingfarescanbemodeledbyassigningfarestotheedges.Figure1displaysthreedifferentassignmentsofweightstotheedgesofagraphrepresentingdistances,flighttimes,andfares,respectively.Graphsthathaveanumberassignedtoeacharecalledweightedgraphs.Weightedgraphsareusedtomodelcomputernetworks.Communicationscosts(suchasthemonthlycostofleasingatelephoneline),theresponsetimesofthecomputersovertheselines,orthedistancebetweencomputer,canallbestudiedusingweightedgraphs,Figure2displayweightedgraphsthatrepresentthreewaystoassignweightstotheedgesofacomputernetwork,correspondingtodistance,responsetime,andcost.Severaltypesofproblemsinvolvingweightedgraphsarisefrequently.Determiningapathofleastlengthbetweentwoverticesinanetworkisonesuchproblem.Tobemorespecific,letthelengthofapathinaweightedgraphbethesumoftheweightsoftheedgesofthispath.(Thereadershouldnotethatthisuseofthetermlengthisdifferentfromtheuseoflengthtodenotethenumberofedgesinapathinagraphwithoutweights.)Thequestionis:Whatisashortestpath,thatis,apathofleastlength,betweentwogivenvertices?Forinstance,intheairlinesystemrepresentedbytheweightedgraphshowninFigure1,whatisashortestpathinairdistancebetweenBostonandLosAngles?Whatcombinationsofflightshasthesmallesttotalflighttime(thatis,totaltimeintheair,notincludingtimebetweenflights)betweenBostonandLosAngels?Whatisthecheapestfarebetweenthesetwocities?Inthecomputernetworkshownin2,whatisaleastexpensivesetoftelephonelinesgivesafastestresponsetimeforcommunicationsbetweenSanFranciscoandNewYork?Whichsetoflineshasashortestoveralldistance?Thereareseveraldifferentalgorithmsthatfindashortestpathbetweentwoverticesinaweightedgraph.WewillpresentanalgorithmdiscoveredbytheDutchmathematicianEdgerDijkstrain1959.Theversionwewilldescribesolvesthisprobleminundirectedweightedgraphswherealltheweightsarepositive.Itiseasytoadaptittosolveshortest-pathproblemsindirectedgraphs.$ChicaSanFrancis$9991:40$erAtlanta$129MiamiLosAngeles$6NewYork$99FARES$$Y92:Boston$ChicaSanFrancis$9991:40$erAtlanta$129MiamiLosAngeles$6NewYork$99FARES$$Y92:Boston$39Anotherimportantproblemsinvolvingweightedgraphsasksforalotofshortesttotallengththatvisitseveryvertexofacompletegraphexactlyonce.Thisisthefamoustravelingsalesmanproblem,whichasksforanorderinwhichasalesmanshouldvisiteachofthecitiesonhisrouteexactlyoncesothathetravelstheminimumtotaldistance.Wewilldiscusstheontravelingsalesmanproblemlaterinthissection.FIGURE2WeightedGraphsModelingaComputerNetwork8.6.2AShortest-PathAlgorithmThereareseveraldifferentalgorithmsthatfindashortestpathbetweentwoverticesinaweightedgraph.WewillpresentanalgorithmdiscoveredbytheDutchmathematicianEdgerDijkstrain1959.Theversionwewilldescribesolvesthisprobleminundirectedweightedgraphswherealltheweightsarepositive.Itiseasytoadaptittosolveshortest-pathproblemsindirectedgraphs.Beforegivingaformalpresentationofthealgorithm,wewillgiveamotivatingexample.EXAMPLE1WhatisthelengthofashortestpathbetweenaandzintheweightedgraphshowninFigure3?FIGHER8-63Solution:Althoughashortestpathiseasilyfoundbyinspection,wewilldevelopsomeideasusefulinunderstandingDijkstra’salgorithm.Wewillsolvethisproblembyfindingthelengthofashortestpathfromatosuccessivevertices,untilzisreached.Theonlypathsstartingatathatcontainnovertexotherthana(untiltheterminalvertexisreached)area,banda,d.Becausethelengthsofa,banda,dare4and2,respectively,itfollowsthatdistheclosestvertextoa.Wecanfindthenextclosestvertexbylookingatallpathsthatgothroughonlyaandd(untiltheterminalvertexisreached).Theshortestsuchpathtobisstilla,b,withlength4,andtheshortestsuchpathtoeisa,d,e,withlength5.Consequently,thenextclosestvertextoaisb.Tofindthethirdclosestvertextoa,weneedtoexamineonlypathsthatgothroughonlya,dandb(untiltheterminalvertexisreached).Thereisapathoflength7tocnamelya,b,candapathoflength6toz,namely,a,d,e,z.Consequently,zisthenextclosestvertextoa,andthelengthofashortestpathtozis6.Example1illustratesthegeneralprinciplesusedinDijkstra’salgorithm.Notethatashortestpathfromatozcouldhavebeenfoundbyinspection.However,inspectionisimpracticalforbothhumansandcomputersforgraphswithlargenumbersofedges.Wewillnowconsiderthegeneralproblemoffindingthelengthofashortestpathbetweenaandzinanundirectedconnectedsimpleweighedgraph.Dijkstra’salgorithmproceedsbyfindingthelengthofashortestpathfromatoafirstvertex,thelengthofashortestpathfromatoasecondvertex,andsoon,untilthelengthofashortestfromatozisfound.Thealgorithmreliesonaseriesofiterations.Adistinguishedsetofverticesisconstructedbyaddingonevertex.Alabelingprocedureiscarriedoutatearthiteration.Inthislabelingprocedure,avertexwislabeledwiththelengthofashortestpathfromatowthatcontainsonlyverticsalreadyinthedistinguishedset.Thevertexaddedtothedistinguishedsetisonewithaminimallabelamongthoseverticesnotalreadyintheset.WenowgivethedetailsofDijkstra’salgorithm.Itbeginsbylabelingawith0andtheotherverticeswith°°.WeusedthenotationL(a)=0andL(v)=sfortheselabelsbefore00anyiterationshavetakenplace(thesubscript0standsforthe"0th”iteration).Theselabelsarethelengthsofshortestpathsfromatothevertices,wherethepathscontainonlythevertexa.(Becausenopathfromatoavertexdifferentfromaexists,^isthelengthofashortestpathbetweenaandthisvertex.)Dijkstra’salgorithmproceedsbyformingadistinguishedsetofvertices.LetSdenotethissetafterkiterationsofthelabelingprocedure.WebeginwithS=4.ThesetSisformedfromSbyaddingavertexunotinSwiththesmallestlabel.OnceuisaddedtoS,weupdatethelabelsofallverticesnotinS,sothatL(v),thelabelofthevertexvatthekthstage,isthelengthofashortestpathfromatovthatcontainsverticesonlyinSk(thatis,verticesthatwerealreadyinthedistinguishedsettogetherwithu).LetvbeavertexnotinS.Toupdatethelabelofv,notethatL^(v)isthelengthofashortestpathfromatovcontainingonlyverticesinS.Theupdatingcanbecarriedoutefficientlywhenthisobservationisused:AshortestpathfromatovcontainingonlyelementsofSkiseitherashortestpathfromatovthatcontainsonlyelementsofS(thatis,thedistinguishedverticesnotincludingu),oritisashortestpathfromatouatthe(k-1)ststagewiththeedge(u,v)added.Inotherwords,L(a,v)=min{l(a,v)L(a,u)+w(u,v)}Thisprocedureisiteratedbysuccessively,addingverticestothedistinguishedsetuntilzisadded.Whenzisaddedtothedistinguishedset,itslabelisthelengthofashortestpathfromatoz.Dijkstra’salgorithmisgiveninAlgorithm1.Laterwewillaproofthatthisalgorithmiscorrect.ALGORITHM1Dijkstra’sAlgorithm.ProcedureDijkkstra(G:weightedconnectedsimplegraph,withallweightspositive)){Ghasverticesa=vv，…=zandweightedw(vv),where{v,v}=sifw(vv)is0,1i,jiji,jnotanedgeinG}Fori:=1tonL(v):=siL(a):=0S:=4{thelabelarenowinitializedsothatthelabelofais0andallotherlabelsares,andSistheemptyset}Whilez史SBeginu:=avertexnotinSwithL(u)minimalS:=S{u}ForallverticesvnotinSIfL(u)+w(u,v)<L(v)thenL(v):=L(u)+w(u,v){thisaddsavertextoSwithminimallabelandupdatethelabelsaverticesnotinS}

FIGURE4UsingDijkstra’sAlgorithmtoFindaShortestPathfromatozillustrateshowDijkstra’salgorithmworks.Afterwards,wewillshowthatthisalgorithmalwaysproducesthelengthofashortestpathbetweentwoverticesinaweightedgraph.EXAMPLE2UseDijkstra’salgorithmtofindthelengthofashortestpathbetweentheverticesaandzintheweightedgraphdisplayedinFigure4(a).Solution:ThestepsusedbyDijkstra’salgorithmtofindashortestpathbetweenaandzareshowninFigure4.AteachiterationofthealgorithmtheverticesofthesetSarecircled.AshortestpathfromatoeachvertexcontainingonlyverticesinSisindicatedforeachiteration.Thealgorithmterminationswhenziscircled.Wefindthatashortestpathfromatozisa,c,b,d,e,zwithlength13.Remark:InperformingDijkstra’salgorithmitissometimesmoreconvenienttokeeptrackoflabelsofverticesineachstepusingatableinsteadofrewardingthegraphforeachstep.Next,weuseaninductiveargumenttoshowthatDijkstra’salgorithmproducesthelengthofashortestpathbetweentwoverticesaandzinanundirectedconnectedweightedgraph.Takeastheinductionhypothesisthefollowingassertion:Atthekthteration.thelabelofeveryvertexvinSisthelengthofashortestpathfromatothisvertex,andthelabelofeveryvertexnoteinSisthelengthofashortestpathfromatothisvertexthatcontainonly(besidesthevertexitself)verticesinS.Whenk=0,beforeanyiterationsarecarriedout,S=4,sothelengthofashortestpathfromatoavertexotherthanaiss.Hence,thebasis,caseistrue.Assumethattheinductivehypothesisholdsforthekthiteration.LetvbethevertexaddedtoSatthe(k+1)stiteration,sovisavertexnotinSattheendofthekthiterationwiththesmallestlabel(inthecaseofties,anyvertexwithsmallerlabelmaybeused).FromtheinductivehypothesisweseethatverticesinSbefore(k+1)stiterationarelabeledwiththelengthofashortestpathfroma.Also,vmustbelabeledwiththelengthofashortestpathtoitfroma.Ifthiswerenotthecase,attheendofthekthiterationtherewouldbeapathoflengthlessthanL(v)isthelengthofashortestpathfromatovcontainingonlyverticesinSafterthekthiteration.LetubethefirstvertexnotinSinsuchapath.ThereisapathwithlengthlessthanL(v)fromatoucontainingonlyverticesofS.Thiscontradictsthechoiceofv.Hence,(i)holdsattheendoft