最短路径文献翻译终极版

1、号090111006O24文献翻译最短通路问题院系名称 信息工程学院专业名称信息与计算科学学生姓名 许秀成指导教师 孙贵玲2021年3月10日单 位 代码01密HUANGIIE S&T COL LEGE黄河科技学院毕业论文文献翻译第1页8. 6最短通路问题8.6.1引言许多问题可以用边上赋权的图来建模。考虑一下航线系统如何建模。如果用顶点表 示城市，用边表示航线。给边赋上城市之间的距离，就可以为涉及距离的问题建模；给 边赋上飞行时间，就可以为涉及飞行时间的问题建模；给边赋上票价，就可以为涉及票 价的问题建模。图8-61显示了给一个图的边赋权的三种不同方式，分别表示距离，飞 行时间和票价

2、。黄河科技学院毕业论文文献翻译第2页图8-61为航线系统建模的带权图给每条边赋上一个数的图称为带权图。带权图用来为计算机网络建模。通信本钱比 如租用线的月租费、计算机在这些线路上的响应时间或是计算机之间的距离等都 可以用带权图来研究。图8-62显示一些带权图，它们表示给计算机的图的边赋权的三 种方式，分别对应本钱、响应时间和距离。与带权图有关的几种类型的问题出现得很多。 确定网络里两个顶点之间长度最短的 通路就是一个这样的问题。说的更具体些，设带权图里一条通路的长度是这条通路上各 边的权的总和。读者应当注意，对术语长度的这种用法，与表示不带权的图的通路里 边数的长度的用法，这两者是不同的。问题

3、是：什么是最短通路，即什么是在两个给 定顶点之间长度最短的通路？例如，在图8-61所示带权图表示的航线系统里，在波士 顿与洛杉矶之间以空中距离计算的最短通路是什么？在波士顿与洛杉矶之间什么样的 航班组合的总飞行时间即在空中的总时间，不包括航班之间的时间最短？在这两个 城市之间的最低费用是多少？黄河科技学院毕业论文文献翻译第3页图8-62为计算机网络建模的带权图在图8-62所示的计算机网络里，连接旧金山的计算机与纽约的计算机所需要的最 廉价的一组线是什么？哪一组线给出旧金山与纽约之间的通信的最短响应时 问？哪一组线有最短的总距离？与带权图有关的另外的一个重要问题是：求访问完全图每个顶点恰好一次的

4、、总长 度最短的回路。这就是著名的旅行商问题，它求一位推销商应当以什么样的顺序来访问 其路程上的每个城市恰好一次，使得他旅行的总距离最短。本节后面将讨论旅行商问题。8.6.2最短通路算法求带权图里两个顶点之间的最短通路有几个不同的算法。下面将给出荷兰数学家E E迪克斯特拉在1959年所发现的一个解决无向带权图中最短通路问题的算法，其中所黄河科技学院毕业论文文献翻译第4页有的权都是正数。可以很容易地将它修改后来解决有向图里的最短通路问题。在给出这个算法的形式化表示之前将给出一个启发性的例子。例1在图863所小的带权图里,a和z之可的最短通路的长度是多少？解 虽然通过观察就容易求出最短通路， 但是

5、需要想出一些有助丁理解迪克施特拉 算法的方法。要解决的问题就是：求从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最靠近的顶点是bo为了找出第三个与a最近的顶点，只需要检查直到到达终点为止只经过了a,d和b的那些通路。存在长度为7到c的通路，即a,b,c,以及长度为6

6、到z的通路，即a,d,e,z。 所以，z是下一个与a最靠近的顶点，而且到z的最短通路的长度为6。例1说明了在迪克斯特拉算法里使用的一般原理。注意通过检查就可能求出从a到z最短通路。不过，无论对人还是对计算机来说，检查边数很多的图都是不切实际的。现在将考虑一般问题：在无向联通简单带权图里，求出a与z之间的最短通路的长 度。迪克斯特拉算法如下进行：求出从a到第一个顶点的最短通路的长度，从a到第二 个顶点最短通路的长度，以此类推，直到求出a到z的最短通路长度为止。这个算法依赖丁一系列的迭代。通过在每次跌代里添加一个顶点来构造出特殊顶点 的集合。在每次跌代里完成一个标记过程。在这个标记过程，只包括特殊

7、顶点的从a到w的最短通路的长度来标记w。添加到特殊顶点集里的顶点是尚在集合之外的那些顶点黄河科技学院毕业论文文献翻译第5页 中带有最小标记的顶点。现在给出迪克斯特拉算法的细节。它首先用0标记a而用00标记其余的顶点。用记号La=0和Lv=*表示在没有发生任何迭代之前的这些标记下标0表示“第0次迭代。这些标记是从a到这些顶点的最短通路的长度，其中这些通路只包含顶点a。 因为不存在a到其他顶点的这种通路，所以 8 是a与这样的顶点之间的最短通路的长 度。迪克斯特拉算法是通过形成特殊顶点的集合来进行的。 设*表示在标记过程k次迭 代之后的特殊顶点集。首先S。=巾。集合&是通过过程把不届丁 &

8、amp;一的带最小标记的 顶点u添加到里形成的，一旦把u添加到Sk里，就更新所有不届丁Sk的顶点的标 记，使得顶点v在第个阶段的标记Lkv是只包含Sk里顶点即已有的特殊点再加上u的、从a到v的最短通路的长度。设v是不届丁Sk的一个顶点。为了更新v的标记，注意Lkv促只包含Sk里k顶点 的从a到v的最短通路，要么是只包含Sk里顶点即不包括u在内的特殊顶点的从a到v的最短通路，要么k-1阶段加上边u,v的从a到u的最短通路。换句话说，L a,v =minLa,v,侦a,u w u,vJ这个过程这样迭代：相继添加顶点到特殊顶点集里，直到添加z为止。当把z添加到特 殊顶点集里时，它的标记就是从a到z的

9、最短通路的长度。在算法1里给出迪克斯特拉 算法。随后将证明这个算法的正确性。算法1迪克施特拉算法Procedure DijkkStraG:所有权都为正数的带权连通简单图 G带有顶点a =v0,v,.= z和权wv,vj,其中假设M,vj不是G里的边，那么wvi,vj=8For i:=1 tonLvi:=00L(a):=0S : =*黄河科技学院毕业论文(文献翻译)第6页(现在初始化标记，使得a的标记为0而所有其余标记为 8,S是空集合WhilezSBeginu:=不届丁S的L(u)最小的一个顶点S : =SUuFor所有不届丁S的顶点vIfL(u) w(u,v) : L(v)thenL(v):

10、=L(u) w(u,v)这样就给S里添加带最小标记的顶点，而且更新不在S里的顶点的标记endL(z)=从a到z的最短通路的长度下面的例子说明迪克施特拉算法是如何工作的。随后我们将证明这个算法总是产生带权图里两个顶点之间最短通路的长度。例2用迪克施特拉算法求图8-64a所示的带权图里顶点a与z之间最短通路的长 度。解 图8-64里显示了迪克斯特拉算法求a与z之间最短通路所用的步骤。在算法的 每次迭代里，用圆圈圈起集合&里的顶点。对每次迭代都标明了只包含Sk里顶点的从a到每个顶点的最短通路。当圆圈圈到z时，算法终止。找到从a到z的最短通路是a,c,b,d,e,长度为13。下一步，用归纳论证

11、来证明迪克斯特拉算法产生无向连通带权图里两个顶点a与z之间最短通路的长度。用以下断言作为归纳假设：在第k次迭代里(i)S里的顶点v(v#0)的标记是从a到这个顶点的最短通路的长度。(ii)不在S里的顶点的标记是(这个顶点自身除外)只包含S里顶点的最短通路的长度。当k =0时，在没有执行任何迭代之前，S =a，所以从a到除a外的顶点的最短通 路长度是 8。设v是第k+1次迭代里添加到S里的顶点，使得v是在第k次迭代结束时 带最小标记的不在S里的顶点不唯一的情形里，可以采用带最小标记的任意顶点。根据归纳假设，可以看出在第kF次迭代之前，S里的顶点都用从a出发的最短通黄河科技学院毕业论文(文献翻译)

12、第7页路的长度来标记图8-64用迪克斯特拉算法求从a到z的最短距离另外，必须用从a到v的最短通路的长度来标记V。假设情况不是这样，那么在第k次迭代结束时，就可能存在包含不在S里的顶点的、长度小丁Lk(v)的通路(因为Lk(v)是 在第k次迭代之后、只包含S里顶点的、从a到v的最短通路的长度)。设u是在这样的 通路里不届丁S的第一个顶点。那么存在一条只包含S里顶点的、从a到u的长度小丁Lk(v)的通路。这与对v的选择相矛盾。因此，在第k+1次迭代时(i)成立。设u是在第k+1次迭代之后不届丁S的一个顶点。只包含S里顶点的从a到u的最 短通路要么包含v、要么不包含v。假设它不包含v,那么根据归纳假

13、设，它的长度是Lk(u)0假设它确实包含v,那么它必然是这样组成的：一条只包含S里除v之外的顶点的、从a到v具有最短可能长度的通路，后面接着从v到u的边。这种情形里它的长度是LJv)+w(v,u)。这样就证明了(ii)为真,因为Lk+(u) = minLk(u),L(v)+w(v,u)。已经证明了定理1.定理1迪克斯特拉算法求出连通简单无向带权图里两个顶点之间最短通路的长度。黄河科技学院毕业论文(文献翻译)第8页现在可以估计迪克斯特拉算法的计算复杂性(就加法和比拟而言)。这个算法使用的迭代次数不超过n-1次，因为在每次迭代里添加一个顶点到特殊顶点集里。假设可以估计每次迭代所使用的运算次数，那么

14、大功告成。可以用不超过n-1次比拟来找出不在Sk里 的带最小标记的顶点。 丁是我们使用一次加法和一次比拟来更新不在Sk中的每一个顶点 的标记，所以在每次迭代里的运算不超过2(n1)次，因为在每次迭代里要更新的标记不 超过n-1个。因为迭代次数不超过n-1次，每次迭代的运算次数不超过2(n1),所以 有下面的定理。定理2迪克斯特拉算法使用O(n2)次运算(加法和比拟)来求出连通简单无向带 权图里两个顶点之间最短通路的长度。来源于：罗森(美).离散数学及其应用.北京：机械工业出版社，2003. 8(6) : 491-496.黄河科技学院毕业论文文献翻译第9页附:英文原文8.6 Shortest-P

15、ath Problems8.6.1 IntroductionMany problems can be modeled using graphs with weights assigned to their edges. As an illustration,consider how an airline system can be modeled. We set up the basic graph model by representing cities byvertices and flights by edges. Problems involving flight time can b

16、e modeled by assigning flight timesto edges. Problems involving fares can be modeled by assigning fares to the edges. Figure 1 displays threedifferent assignments of weights to the edges of a graph representing distances, flight times, and fares,respectively.Graphs that have a number assigned to eac

17、h are called weightedweighted graphs.graphs. Weighted graphs are used tomodel computer networks. Communications costs (such as the monthly cost of leasing a telephone line),theresponse times of the computers over these lines, or the distance between computer, can all be studiedusing weighted graphs,

18、 Figure 2 display weighted graphs that represent three ways to assign weights tothe edges of a computer network, corresponding to distance, response time, and cost.Several types of problems involving weighted graphs arise frequently. Determining a path of leastlength between two vertices in a networ

19、k is one such problem. To be more specific, let the lengthlength of apath in a weighted graph be the sum of the weights of the edges of this path.(The reader should note thatthis use of the term length is different from the use of length to denote the number of edges in a pathin a graph without weig

20、hts.)黄河科技学院毕业论文文献翻译第10页The question is: What is a shortest path, that is, a path of least length, between two given vertices?For instance, in the airline system representedby the weighted graph shown in Figure 1, what is a shortestpath in air distance between Boston and Los Angles? What combinations

21、 of flights has the smallest totalflight time (that is, total time in the air, not including time between flights) between Boston and LosAngels? What is the cheapest fare between these two cities? In the computer network shown in 2, what isa least expensive set of telephone lines gives a fastest res

22、ponse time for communications between SanFrancisco and New York? Which set of lines has a shortest overall distance?There are several different algorithms that find a shortest path between two vertices in a weightedgraph. We will present an algorithm discovered by the Dutch mathematician Edger Dijks

23、tra in 1959. The versionwe will describe solves this problem in undirected weighted graphs where all the weights are positive.It is easy to adapt it to solve shortest-path problems in directed graphs.FLIGHT TIMES4:02:1Boston0:50San Francisco.Chicag342:22:551:401:5550New York2:45AtlantaLos Angeles1:3

24、0Miami黄河科技学院毕业论文文献翻译第11页LosAnother important problems involving weighted graphs asks for a lot of shortest total length thatvisits every vertex of a complete graph exactly once. This is the famoutraveling salesman problem,whichasks for an order in which a salesman should visit each of the cities on

25、his route exactly once so thathe travels the minimum total distance. We will discuss the on traveling salesman problem later in thissection.DISTANCE957 DenverDallasBostonSan F1855Chicago722191New York3491736/ 798451372FIGURE 8-61 Weighted Graphs Modeling an Airline System黄河科技学院毕业论文文献翻译第12页FIGURE 2 W

26、eighted Graphs Modeling a Computer Network8.6.2 A Shortest-Path AlgorithmThere are several different algorithms that find a shortest path between two vertices in a weighted graph.We will present an algorithm discovered by the Dutch mathematician Edger Dijkstra in 1959. The version we willdescribe so

27、lves this problem in undirected weighted graphs where all the weights are positive. It is easy to adaptit to solve shortest-path problems in directed graphs.Before giving a formal presentation of the algorithm, we will give a motivating example. EXAMPLE 1 What isthe length of a shortest path between

28、aandzin the weighted graph shown in Figure 3?RESPONSE TIMEBostonDallas黄河科技学院毕业论文文献翻译第13页FIGHER 8-63Solution: Although a shortest path is easily found by inspection , we will develop some ideas useful in understandingDijkstra s algorithm. We will solve this problem by finding the lengthof a shortest

29、path fromato successive vertices, untilzis reached.The only paths starting atathat contain no vertex other thana(until the terminal vertex is reached) area, banda, d. Because the lengths ofa,banda, dare 4 and 2, respectively, it follows that d is the closest vertextoa.We can find the next closest ve

30、rtex by looking at all paths that go through onlyaand d (until the terminalvertex is reached). The shortest such path to b is stilla, b, with length 4,and the shortest such path toeisa,d,e, with length 5.Consequently, the next closest vertex toais b.To find the third closest vertex toa, we need to e

31、xamine only paths that go through onlya,dand b (untilthe terminal vertex is reached). There is a path of length 7 to c namelya,b,cand a path of length 6 toz, namely,a,d,e,z.Consequently,zis the next closest vertex toa, and the length of a shortest path tozis 6.Example 1illustrates the general princi

32、ples used in Dijkstra s algorithm. Notshortest path fromatozcould have been found by inspection. However, inspection is impractical for both humansand computers for graphs with large numbers of edges.We will now consider the general problem of finding the length of a shortest path betweenaandzin an

33、undirectedconnected simple weighed graph. Dijkstra algorithm proceeds by finding the length of a shortest path fromatoa first vertex, the length of a shortest path fromato a second vertex, and so on, until the length of a shortestfromatozis found.The algorithm relies on a series of iterations. A dis

34、tinguished set of vertices is constructed by adding onevertex. A labeling procedure is carried out at earth iteration. In this labeling procedure, a vertexwis labeledwith the length of a shortest path fromatowthat contains only vertics already in the distinguished set. Thevertex added to the disting

35、uished set is one with a minimal label among those vertices not already in the set.We now give the details of Dijkstra s algorithm. It begins by la/beHir0gand theother vertices with00. We used the notationL0(a) =0 and L()(v)=叫for these labels before any iterations havetaken place (the subscript 0 st

36、ands for th “0th iteration). These labels are the lengths of shortest paths from黄河科技学院毕业论文文献翻译第14页ato the vertices, where the paths contain only the vertexa.(Because no path fromato a vertex different fromaexists,00is the length of a shortest path betweenaand this vertex.)Dijkstra s algorithm procee

37、ds by forming a digtished set of vertices. LetSkdenote this set after k iterationsof the labeling procedure. We begin withSo =. The setSkis formed fromSk4by adding a vertexunot inSkJwiththe smallest label. Onceuis added toSk, we update the labels of all vertices not inSk, so thatLk(v),the labelof th

38、e vertexvat thekthstage, is the length of a shortest path fromatovthat contains vertices only inSk(that is, vertices that were already in the distinguished set together withu).Letvbe a vertex not inSk. To update the label ofv, note thatLk(v)is the length of a shortest path fromatovcontaining only ve

39、rtices inSk. The updating can be carried out efficiently when this observation is used:A shortest path fromatovcontaining only elements ofSkis either a shortest path fromatovthat contains onlyelements ofSk4(that is, the distinguished vertices not includingu), or it is a shortest path fromatou黄河科技学院毕

40、业论文(文献翻译) 第15页at the(k -1)st stage with the edgu,v)added. In other words,L a,v = min.Lka, v ,Lka,u w u,v /This procedure is iterated by successively, adding vertices to the distinguished set untilzis added. Whenzisadded to the distinguished set, its label is the length of a shortest path fromatoz.Di

41、jkstraalgorithm is givenin Algorithm 1. Later we will a proof that this algorithm is correct.ALGORITHMALGORITHM 1 1 DijkstraDijkstra s s Algorithm.Algorithm.Procedure Dijkkstra(G :weighted connected simple graph, with all weights positive)G has vertices a = v0,v1,.= z and weighted w(vi,vj), where v.

42、 =00if w(vi,vj) isnot an edge in GFor i:=1 tonL(vi) :=00L(a):=0S := the label are now initialized so that the label ofais 0 and all other labels are S is ,and the empty set WhilezS Beginu:=a vertex not in S withL(u)minimalS :=SUuFor all verticesvnot in SIfL(u) w(u,v) L(v)thenL(v):=L(u) w(u,v)this ad

43、ds a vertex to S with minimal label and update the labels a vertices not in S黄河科技学院毕业论文文献翻译第16页FIGURE 4 Using Dijkstras Algorithm to Find a Shortest Path from a to z illustrates how Dijkstra algorithmworks. Afterwards, we will show that this algorithm always produces the length of a shortest path be

44、tween two verticesin a weighted graph. EXAMPLE 2 Use Dijkstra algorithm to find the length of a shortest path between the verticesa andzin the weighted graph displayed in Figure 4(a).Solution: The steps used by Dijkstra s algo o rfthma shortest path between a andzare shown in Figure 4.Ateachiteratio

45、n of the algorithm the vertices of the setSkare circled.A shortest path from a to each vertex containing only vertices inSkis indicated for each iteration. The algorithmterminations whenzis circled. We find that a shortest path from a to z isa,c,b,d,e,zwith length 13.RemarkRemark: In performing Dijk

46、stra s algorithm it is sometimes more convenient to keep track oflabels of vertices in each step using a table instead of rewarding the graph for each step.Next, we use an inductive argument to show that Dijkstra algorithm produces the length of a shortest pathbetween two vertices a and zin an undir

47、ected connected weighted graph. Take as the induction hypothesis the followingassertion: At thekth teration.(i)the label of every vertex v in S is the length of a shortest path from a to this vertex ,and(ii)the label of every vertex note in S is the length of a shortest path fromato this vertex that

48、 contain黄河科技学院毕业论文文献翻译第17页only(besides the vertex itself) vertices in S.Whenk= 0 , before any iterations are carried outS = , so the length of a shortest path from a to a vertex otherthan a is二.Hence, the basis, case is true.Assume that the inductive hypothesis holds for the kth iteration. Let v be

49、the vertex added to Sat the(k 1)st iteration, so v is a vertex not in S at the end of thekth iteration with the smallest label (in the case ofties, any vertex with smaller label may be used).From the inductive hypothesis we see that vertices in S before (k 1 )st iteration are labeled with the length

50、of a shortest path from a .Also, v must be labeled with the length of a shortest path to it from a . If this werenot the case, at the end of thekthiteration there would be a path of length less than L(k)(v) is the length ofa shortest path from a to v containing only vertices in S after thekthiteration. Let u be the first vertex notin S in such a path. There is a path with length less than L(k)(v) from a to u containing only vertices of S. Thiscontradicts the choice ofv. Hence,(i)holds at the end of the(k 1)st iteration.Let u be a verte