最短路徑文獻翻譯終極版

1、號090111006O24文獻翻譯最短通路問題院系名稱 信息工程學(xué)院專業(yè)名稱信息與計算科學(xué)學(xué)生姓名 許秀成指導(dǎo)教師 孫貴玲2021年3月10日單 位 代碼01密HUANGIIE S&T COL LEGE黃河科技學(xué)院畢業(yè)論文文獻翻譯第1頁8. 6最短通路問題8.6.1引言許多問題可以用邊上賦權(quán)的圖來建模。考慮一下航線系統(tǒng)如何建模。如果用頂點表 示城市，用邊表示航線。給邊賦上城市之間的距離，就可以為涉及距離的問題建模；給 邊賦上飛行時間，就可以為涉及飛行時間的問題建模；給邊賦上票價，就可以為涉及票 價的問題建模。圖8-61顯示了給一個圖的邊賦權(quán)的三種不同方式，分別表示距離，飛 行時間和票價

2、。黃河科技學(xué)院畢業(yè)論文文獻翻譯第2頁圖8-61為航線系統(tǒng)建模的帶權(quán)圖給每條邊賦上一個數(shù)的圖稱為帶權(quán)圖。帶權(quán)圖用來為計算機網(wǎng)絡(luò)建模。通信本錢比 如租用線的月租費、計算機在這些線路上的響應(yīng)時間或是計算機之間的距離等都 可以用帶權(quán)圖來研究。圖8-62顯示一些帶權(quán)圖，它們表示給計算機的圖的邊賦權(quán)的三 種方式，分別對應(yīng)本錢、響應(yīng)時間和距離。與帶權(quán)圖有關(guān)的幾種類型的問題出現(xiàn)得很多。 確定網(wǎng)絡(luò)里兩個頂點之間長度最短的 通路就是一個這樣的問題。說的更具體些，設(shè)帶權(quán)圖里一條通路的長度是這條通路上各 邊的權(quán)的總和。讀者應(yīng)當(dāng)注意，對術(shù)語長度的這種用法，與表示不帶權(quán)的圖的通路里 邊數(shù)的長度的用法，這兩者是不同的。問題

3、是：什么是最短通路，即什么是在兩個給 定頂點之間長度最短的通路？例如，在圖8-61所示帶權(quán)圖表示的航線系統(tǒng)里，在波士 頓與洛杉磯之間以空中距離計算的最短通路是什么？在波士頓與洛杉磯之間什么樣的 航班組合的總飛行時間即在空中的總時間，不包括航班之間的時間最短？在這兩個 城市之間的最低費用是多少？黃河科技學(xué)院畢業(yè)論文文獻翻譯第3頁圖8-62為計算機網(wǎng)絡(luò)建模的帶權(quán)圖在圖8-62所示的計算機網(wǎng)絡(luò)里，連接舊金山的計算機與紐約的計算機所需要的最 廉價的一組線是什么？哪一組線給出舊金山與紐約之間的通信的最短響應(yīng)時 問？哪一組線有最短的總距離？與帶權(quán)圖有關(guān)的另外的一個重要問題是：求訪問完全圖每個頂點恰好一次的

4、、總長 度最短的回路。這就是著名的旅行商問題，它求一位推銷商應(yīng)當(dāng)以什么樣的順序來訪問 其路程上的每個城市恰好一次，使得他旅行的總距離最短。本節(jié)后面將討論旅行商問題。8.6.2最短通路算法求帶權(quán)圖里兩個頂點之間的最短通路有幾個不同的算法。下面將給出荷蘭數(shù)學(xué)家E E迪克斯特拉在1959年所發(fā)現(xiàn)的一個解決無向帶權(quán)圖中最短通路問題的算法，其中所黃河科技學(xué)院畢業(yè)論文文獻翻譯第4頁有的權(quán)都是正數(shù)?？梢院苋菀椎貙⑺薷暮髞斫鉀Q有向圖里的最短通路問題。在給出這個算法的形式化表示之前將給出一個啟發(fā)性的例子。例1在圖863所小的帶權(quán)圖里,a和z之可的最短通路的長度是多少？解 雖然通過觀察就容易求出最短通路， 但是

5、需要想出一些有助丁理解迪克施特拉 算法的方法。要解決的問題就是：求從a到各個相繼的頂點的最短通路，直到到達(dá)z為 止。從a開始、直到到達(dá)終點為止不包括除a以外的頂點的唯一通路是a, b和a, d。 因為a, b和a, d的長度分別是4和2,所以d是與a最近的頂點?？梢酝ㄟ^查看直到到達(dá)終點為止只經(jīng)過a和d的所有通路，來求出下一個最靠 近a的頂點。到b的最短通路仍然是a , b ,長度為4,而到e的最短通路是a,d,e,長 度為5。所以，下一個與a最靠近的頂點是bo為了找出第三個與a最近的頂點，只需要檢查直到到達(dá)終點為止只經(jīng)過了a,d和b的那些通路。存在長度為7到c的通路，即a,b,c,以及長度為6

6、到z的通路，即a,d,e,z。 所以，z是下一個與a最靠近的頂點，而且到z的最短通路的長度為6。例1說明了在迪克斯特拉算法里使用的一般原理。注意通過檢查就可能求出從a到z最短通路。不過，無論對人還是對計算機來說，檢查邊數(shù)很多的圖都是不切實際的。現(xiàn)在將考慮一般問題：在無向聯(lián)通簡單帶權(quán)圖里，求出a與z之間的最短通路的長 度。迪克斯特拉算法如下進行：求出從a到第一個頂點的最短通路的長度，從a到第二 個頂點最短通路的長度，以此類推，直到求出a到z的最短通路長度為止。這個算法依賴丁一系列的迭代。通過在每次跌代里添加一個頂點來構(gòu)造出特殊頂點 的集合。在每次跌代里完成一個標(biāo)記過程。在這個標(biāo)記過程，只包括特殊

7、頂點的從a到w的最短通路的長度來標(biāo)記w。添加到特殊頂點集里的頂點是尚在集合之外的那些頂點黃河科技學(xué)院畢業(yè)論文文獻翻譯第5頁 中帶有最小標(biāo)記的頂點?，F(xiàn)在給出迪克斯特拉算法的細(xì)節(jié)。它首先用0標(biāo)記a而用00標(biāo)記其余的頂點。用記號La=0和Lv=*表示在沒有發(fā)生任何迭代之前的這些標(biāo)記下標(biāo)0表示“第0次迭代。這些標(biāo)記是從a到這些頂點的最短通路的長度，其中這些通路只包含頂點a。 因為不存在a到其他頂點的這種通路，所以 8 是a與這樣的頂點之間的最短通路的長 度。迪克斯特拉算法是通過形成特殊頂點的集合來進行的。 設(shè)*表示在標(biāo)記過程k次迭 代之后的特殊頂點集。首先S。=巾。集合&是通過過程把不屆丁 &

8、amp;一的帶最小標(biāo)記的 頂點u添加到里形成的，一旦把u添加到Sk里，就更新所有不屆丁Sk的頂點的標(biāo) 記，使得頂點v在第個階段的標(biāo)記Lkv是只包含Sk里頂點即已有的特殊點再加上u的、從a到v的最短通路的長度。設(shè)v是不屆丁Sk的一個頂點。為了更新v的標(biāo)記，注意Lkv促只包含Sk里k頂點 的從a到v的最短通路，要么是只包含Sk里頂點即不包括u在內(nèi)的特殊頂點的從a到v的最短通路，要么k-1階段加上邊u,v的從a到u的最短通路。換句話說，L a,v =minLa,v,偵a,u w u,vJ這個過程這樣迭代：相繼添加頂點到特殊頂點集里，直到添加z為止。當(dāng)把z添加到特 殊頂點集里時，它的標(biāo)記就是從a到z的

9、最短通路的長度。在算法1里給出迪克斯特拉 算法。隨后將證明這個算法的正確性。算法1迪克施特拉算法Procedure DijkkStraG:所有權(quán)都為正數(shù)的帶權(quán)連通簡單圖 G帶有頂點a =v0,v,.= z和權(quán)wv,vj,其中假設(shè)M,vj不是G里的邊，那么wvi,vj=8For i:=1 tonLvi:=00L(a):=0S : =*黃河科技學(xué)院畢業(yè)論文(文獻翻譯)第6頁(現(xiàn)在初始化標(biāo)記，使得a的標(biāo)記為0而所有其余標(biāo)記為 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里添加帶最小標(biāo)記的頂點，而且更新不在S里的頂點的標(biāo)記endL(z)=從a到z的最短通路的長度下面的例子說明迪克施特拉算法是如何工作的。隨后我們將證明這個算法總是產(chǎn)生帶權(quán)圖里兩個頂點之間最短通路的長度。例2用迪克施特拉算法求圖8-64a所示的帶權(quán)圖里頂點a與z之間最短通路的長 度。解 圖8-64里顯示了迪克斯特拉算法求a與z之間最短通路所用的步驟。在算法的 每次迭代里，用圓圈圈起集合&里的頂點。對每次迭代都標(biāo)明了只包含Sk里頂點的從a到每個頂點的最短通路。當(dāng)圓圈圈到z時，算法終止。找到從a到z的最短通路是a,c,b,d,e,長度為13。下一步，用歸納論證

11、來證明迪克斯特拉算法產(chǎn)生無向連通帶權(quán)圖里兩個頂點a與z之間最短通路的長度。用以下斷言作為歸納假設(shè)：在第k次迭代里(i)S里的頂點v(v#0)的標(biāo)記是從a到這個頂點的最短通路的長度。(ii)不在S里的頂點的標(biāo)記是(這個頂點自身除外)只包含S里頂點的最短通路的長度。當(dāng)k =0時，在沒有執(zhí)行任何迭代之前，S =a，所以從a到除a外的頂點的最短通 路長度是 8。設(shè)v是第k+1次迭代里添加到S里的頂點，使得v是在第k次迭代結(jié)束時 帶最小標(biāo)記的不在S里的頂點不唯一的情形里，可以采用帶最小標(biāo)記的任意頂點。根據(jù)歸納假設(shè)，可以看出在第kF次迭代之前，S里的頂點都用從a出發(fā)的最短通黃河科技學(xué)院畢業(yè)論文(文獻翻譯)

12、第7頁路的長度來標(biāo)記圖8-64用迪克斯特拉算法求從a到z的最短距離另外，必須用從a到v的最短通路的長度來標(biāo)記V。假設(shè)情況不是這樣，那么在第k次迭代結(jié)束時，就可能存在包含不在S里的頂點的、長度小丁Lk(v)的通路(因為Lk(v)是 在第k次迭代之后、只包含S里頂點的、從a到v的最短通路的長度)。設(shè)u是在這樣的 通路里不屆丁S的第一個頂點。那么存在一條只包含S里頂點的、從a到u的長度小丁Lk(v)的通路。這與對v的選擇相矛盾。因此，在第k+1次迭代時(i)成立。設(shè)u是在第k+1次迭代之后不屆丁S的一個頂點。只包含S里頂點的從a到u的最 短通路要么包含v、要么不包含v。假設(shè)它不包含v,那么根據(jù)歸納假

13、設(shè)，它的長度是Lk(u)0假設(shè)它確實包含v,那么它必然是這樣組成的：一條只包含S里除v之外的頂點的、從a到v具有最短可能長度的通路，后面接著從v到u的邊。這種情形里它的長度是LJv)+w(v,u)。這樣就證明了(ii)為真,因為Lk+(u) = minLk(u),L(v)+w(v,u)。已經(jīng)證明了定理1.定理1迪克斯特拉算法求出連通簡單無向帶權(quán)圖里兩個頂點之間最短通路的長度。黃河科技學(xué)院畢業(yè)論文(文獻翻譯)第8頁現(xiàn)在可以估計迪克斯特拉算法的計算復(fù)雜性(就加法和比擬而言)。這個算法使用的迭代次數(shù)不超過n-1次，因為在每次迭代里添加一個頂點到特殊頂點集里。假設(shè)可以估計每次迭代所使用的運算次數(shù)，那么

14、大功告成?？梢杂貌怀^n-1次比擬來找出不在Sk里 的帶最小標(biāo)記的頂點。 丁是我們使用一次加法和一次比擬來更新不在Sk中的每一個頂點 的標(biāo)記，所以在每次迭代里的運算不超過2(n1)次，因為在每次迭代里要更新的標(biāo)記不 超過n-1個。因為迭代次數(shù)不超過n-1次，每次迭代的運算次數(shù)不超過2(n1),所以 有下面的定理。定理2迪克斯特拉算法使用O(n2)次運算(加法和比擬)來求出連通簡單無向帶 權(quán)圖里兩個頂點之間最短通路的長度。來源于：羅森(美).離散數(shù)學(xué)及其應(yīng)用.北京：機械工業(yè)出版社，2003. 8(6) : 491-496.黃河科技學(xué)院畢業(yè)論文文獻翻譯第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.)黃河科技學(xué)院畢業(yè)論文文獻翻譯第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黃河科技學(xué)院畢業(yè)論文文獻翻譯第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黃河科技學(xué)院畢業(yè)論文文獻翻譯第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黃河科技學(xué)院畢業(yè)論文文獻翻譯第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黃河科技學(xué)院畢業(yè)論文文獻翻譯第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黃河科技學(xué)院畢

40、業(yè)論文(文獻翻譯) 第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黃河科技學(xué)院畢業(yè)論文文獻翻譯第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黃河科技學(xué)院畢業(yè)論文文獻翻譯第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