最短路徑文獻翻譯終極版

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

2、行時間和票價。圖8-61 為航線系統(tǒng)建模的帶權(quán)圖給每條邊賦上一個數(shù)的圖稱為帶權(quán)圖。帶權(quán)圖用來為計算機網(wǎng)絡建模。通信成本（比 如租用電話線的月租費）、計算機在這些線路上的響應時間或是計算機之間的距離等都 可以用帶權(quán)圖來研究。圖8-62顯示一些帶權(quán)圖，它們表示給計算機的圖的邊賦權(quán)的三 種方式，分別對應成本、響應時間和距離。與帶權(quán)圖有關(guān)的幾種類型的問題出現(xiàn)得很多。 確定網(wǎng)絡里兩個頂點之間長度最短的 通路就是一個這樣的問題。說的更具體些，設帶權(quán)圖里一條通路的長度是這條通路上各 邊的權(quán)的總和。（讀者應當注意，對術(shù)語長度的這種用法，與表示不帶權(quán)的圖的通路里 邊數(shù)的長度的用法，這兩者是不同的。）問題是：什么

3、是最短通路，即什么是在兩個給 定頂點之間長度最短的通路？例如，在圖8-61所示帶權(quán)圖表示的航線系統(tǒng)里，在波士 頓與洛杉磯之間以空中距離計算的最短通路是什么？在波士頓與洛杉磯之間什么樣的 航班組合的總飛行時間（即在空中的總時間，不包括航班之間的時間）最短？在這兩個 城市之間的最低費用是多少？圖8-62為計算機網(wǎng)絡建模的帶權(quán)圖在圖8-62所示的計算機網(wǎng)絡里，連接舊金山的計算機與紐約的計算機所需要的最 便宜的一組電話線是什么？哪一組電話線給出舊金山與紐約之間的通信的最短響應時 問？哪一組電話線有最短的總距離？與帶權(quán)圖有關(guān)的另外的一個重要問題是：求訪問完全圖每個頂點恰好一次的、總長 度最短的回路。這就

4、是著名的旅行商問題，它求一位推銷商應當以什么樣的順序來訪問 其路程上的每個城市恰好一次，使得他旅行的總距離最短。本節(jié)后面將討論旅行商問題。 8.6.2最短通路算法求帶權(quán)圖里兩個頂點之間的最短通路有幾個不同的算法。下面將給出荷蘭數(shù)學家E 迪克斯特拉在1959年所發(fā)現(xiàn)的一個解決無向帶權(quán)圖中最短通路問題的算法，其中所有的權(quán)都是正數(shù)。可以很容易地將它修改后來解決有向圖里的最短通路問題。在給出這個算法的形式化表示之前將給出一個啟發(fā)性的例子。例1 在圖863所小的帶權(quán)圖里,a和z之可的最短通路的長度是多少？解 雖然通過觀察就容易求出最短通路， 但是需要想出一些有助丁理解迪克施特拉 算法的辦法。要解決的問題

5、就是：求從 a到各個相繼的頂點的最短通路，直到到達 z為 止。從a開始、（直到到達終點為止）不包括除a以外的頂點的唯一通路是a, b和a, d。 因為a, b和a, d的長度分別是4和2,所以d是與a最近的頂點。可以通過查看（直到到達終點為止）只經(jīng)過 a和d的所有通路，來求出下一個最靠 近a的頂點。到b的最短通路仍然是a , b ,長度為4,而到e的最短通路是a, d,e,長 度為5。所以，下一個與a最靠近的頂點是bo為了找出第三個與a最近的頂點，只需要檢查（直到到達終點為止）只經(jīng)過了 a,d和 b的那些通路。存在長度為7到c的通路，即a,b,c,以及長度為6到z的通路，即a,d,e,z。 所

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

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

8、mp;是通過過程把不屆丁 &一的帶最小標記的 頂點u添加到里形成的，一旦把u添加到Sk里，就更新所有不屆丁 Sk的頂點的標 記，使得頂點v在第個階段的標記Lk（v ）是只包含Sk里頂點（即已有的特殊點再加上u） 的、從a到v的最短通路的長度。設v是不屆丁 Sk的一個頂點。為了更新v的標記，注意Lk（v促只包含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,v J這個過程這樣迭代：相繼添加頂點到特殊頂點集里，直到添加

9、 z為止。當把z添加到特 殊頂點集里時，它的標記就是從a到z的最短通路的長度。在算法1里給出迪克斯特拉 算法。隨后將證明這個算法的正確性。算法1迪克施特拉算法Procedure DijkkStra（G :所有權(quán)都為正數(shù)的帶權(quán)連通簡單圖） G帶有頂點a =v0,v,. = z和權(quán)w（v,vj）,其中若M,vj不是G里的邊，則w（vi,vj）=8For i:=1 to nL（vi） := 00L(a) :=0S : =*黃河科技學院畢業(yè)論文(文獻翻譯)第 8頁(現(xiàn)在初始化標記，使得a的標記為0而所有其余標記為8, S是空集合While zSBeginu :=不屆丁 S的L(u)最小的一個頂點S :

10、 =SUuFor所有不屆丁 S的頂點vIf L(u) w(u,v) : L(v) then L(v):=L(u) w(u,v)這樣就給S里添加帶最小標記的頂點，而且更新不在 S里的頂點的標記end L(z)=從a到z的最短通路的長度下面的例子說明迪克施特拉算法是如何工作的。隨后我們將證明這個算法總是產(chǎn)生帶權(quán)圖里兩個頂點之間最短通路的長度。例2用迪克施特拉算法求圖8-64a所示的帶權(quán)圖里頂點a與z之間最短通路的長 度。解 圖8-64里顯示了迪克斯特拉算法求a與z之間最短通路所用的步驟。在算法的 每次迭代里，用圓圈圈起集合&里的頂點。對每次迭代都標明了只包含Sk里頂點的從a 到每個頂點的最

11、短通路。當圓圈圈到z時，算法終止。找到從 a到z的最短通路是a,c,b,d,e,長度為 13。下一步，用歸納論證來證明迪克斯特拉算法產(chǎn)生無向連通帶權(quán)圖里兩個頂點a與z之間最短通路的長度。用下列斷言作為歸納假設：在第k次迭代里(i) S里的頂點v(v#0)的標記是從a到這個頂點的最短通路的長度。(ii) 不在S里的頂點的標記是(這個頂點自身除外)只包含S里頂點的最短通路的長度。當k =0時，在沒有執(zhí)行任何迭代之前，S =a，所以從a到除a外的頂點的最短通 路長度是8。設v是第k+1次迭代里添加到S里的頂點，使得v是在第k次迭代結(jié)束時 帶最小標記的不在S里的頂點不唯一的情形里，可以采用帶最小標記的

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

13、含S里頂點的從a到u的最 短通路要么包含v、要么不包含v。若它不包含v,則根據(jù)歸納假設，它的長度是Lk(u)0 若它確實包含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)圖里兩個頂點之間最短通路的長度?，F(xiàn)在可以估計迪克斯特拉算法的計算復雜性(就加法和比較而言)。這個算法使用的迭代次數(shù)不超過n-1次，因為在每次迭代里添加一個頂點到特

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

15、文獻翻譯）第 10頁附:英文原文8.6 Shortest-Path 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 by vertices and flights by edges. Prob

16、lems involving flight time can be modeled by assigning flight times to edges. Problems involving fares can be modeled by assigning fares to the edges. Figure 1 displays three different assignments of weights to the edges of a graph representing distances, flight times, and fares, respectively.Graphs

17、 that have a number assigned to each are called weighted graphs. Weighted graphs are used to model computer networks. Communications costs (such as the monthly cost of leasing a telephone line),the response times of the computers over these lines, or the distance between computer, can all be studied

18、 using weighted graphs, Figure 2 display weighted graphs that represent three ways to assign weights to the 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 least length between

19、 two vertices in a network is one such problem. To be more specific, let the length of a path in a weighted graph be the sum of the weights of the edges of this path.(The reader should note that this use of the term length is different from the use of length to denote the number of edges in a path i

20、n a graph without weights.)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 shortest path in air distance between Boston and Los Angles? What combin

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

22、stest response time for communications between San Francisco and New York? Which set of lines has a shortest overall distance?FLIGHT TIMES4:02:1Boston0:50San Francisco.Chicag342:22:551:401:5550New York2:45AtlantaLos Angeles1:30MiamiThere are several different algorithms that find a shortest path bet

23、ween two vertices in a weighted graph. We will present an algorithm discovered by the Dutch mathematician Edger Dijkstra in 1959. The version we 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

24、in directed graphs.黃河科技學院畢業(yè)論文（文獻翻譯）第11頁FIGURE 8-61 Weighted Graphs Modeling an Airline SystemBostonSan F1855Chicago722191New YorkAnother important problems involving weighted graphs asks for a lot of shortest total length that visits every vertex of a complete graph exactly once. This is the famoutr

25、aveling salesman problem,which asks for an order in which a salesman should visit each of the cities on his route exactly once so that he travels the minimum total distance. We will discuss the on traveling salesman problem later in this section.DISTANCELos957 Denver3491736/ 798451372Dallas黃河科技學院畢業(yè)論

26、文（文獻翻譯）第 14頁RESPONSE TIMEBostonDallasFIGURE 2 Weighted 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

27、Dijkstra in 1959. The version we 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.Before giving a formal presentation of the algorithm, we will give a motivating example. EXAM

28、PLE 1 What is the length of a shortest path between a and z in the weighted graph shown in Figure 3?FIGHER 8-63Solution: Although a shortest path is easily found by inspection , we will develop some ideas useful in understanding Dijkstra' s algorithm. We will solve this problem by finding the le

29、ngthof a shortest path from a to successive vertices, until z is reached.The only paths starting at a that contain no vertex other than a (until the terminal vertex is reached) are a, b anda, d . Because the lengths of a,b and a, d are 4 and 2, respectively, it follows that d is the closest vertex t

30、o a .We can find the next closest vertex by looking at all paths that go through only a and d (until the terminal vertex is reached). The shortest such path to b is still a, b , with length 4,and the shortest such path to e is a,d,e, with length 5.Consequently, the next closest vertex to a is b.To f

31、ind the third closest vertex to a , we need to examine only paths that go through only a,d and b (until the terminal vertex is reached). There is a path of length 7 to c namely a,b,c and a path of length 6 to z, namely,a,d,e,z. Consequently, z is the next closest vertex to a , and the length of a sh

32、ortest path to z is 6.Example 1 illustrates the general principles used in Dijkstra' s algorithm. Notshortest path from a to z could have been found by inspection. However, inspection is impractical for both humans and computers for graphs with large numbers of edges.We will now consider the gen

33、eral problem of finding the length of a shortest path between a and z in an undirected connected simple weighed graph. Dijkstra algorithm proceeds by finding the length of a shortest path from a to a first vertex, the length of a shortest path from a to a second vertex, and so on, until the length o

34、f a shortest from a to z is found.The algorithm relies on a series of iterations. A distinguished set of vertices is constructed by adding one vertex. A labeling procedure is carried out at earth iteration. In this labeling procedure, a vertex w is labeled with the length of a shortest path from a t

35、o w that contains only vertics already in the distinguished set. The vertex added to the distinguished 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 with 00. We used the n

36、otation L0(a) = 0 and L()(v)=叫 for these labels before any iterations have taken place (the subscript 0 stands for th “0th " iteration). These labels are the lengths of shortest paths from a to the vertices, where the paths contain only the vertex a .(Because no path from a to a vertex differen

37、t from a exists, 00 is the length of a shortest path between a and this vertex.)Dijkstra ' s algorithm proceeds by forming a digtished set of vertices. Let Sk denote this set after k iterations of the labeling procedure. We begin with So = . The set Sk is formed from Sk4 by adding a vertex u not

38、 in SkJ with the smallest label. Once u is added to Sk, we update the labels of all vertices not in Sk, so that Lk(v) ,the label of the vertex v at the kth stage, is the length of a shortest path from a to v that contains vertices only in Sk (that is, vertices that were already in the distinguished

39、set together with u).Let v be a vertex not inSk. To update the label of v, note that Lk(v) is the length of a shortest path from a to v containing only vertices in Sk. The updating can be carried out efficiently when this observation is used: A shortest path from a to v containing only elements of S

40、k is either a shortest path from a to v that contains only elements ofSk 4 (that is, the distinguished vertices not including u ), or it is a shortest path from a to u 黃河科技學院畢業(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 proced

41、ure is iterated by successively, adding vertices to the distinguished set until z is added. When z is added to the distinguished set, its label is the length of a shortest path from a to z.Dijkstra algorithm is given in Algorithm 1. Later we will a proof that this algorithm is correct.ALGORITHM 1 Di

42、jkstra ' s 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. = 00 if w(vi,vj) isnot an edge in GFor i:=1 to nL(vi) := 00L(a) :=0S := the label are now initialized so that the label of a is 0 a

43、nd all other labels are S is ,and the empty set While zS Beginu:=a vertex not in S with L(u) minimalS : =SUuFor all vertices v not in SIf L(u) w(u,v) < L(v) then L(v):=L(u) w(u,v)this adds a vertex to S with minimal label and update the labels a vertices not in S黃河科技學院畢業(yè)論文（文獻翻譯）第 18頁FIGURE 4 Usin

44、g Dijkstra's Algorithm to Find a Shortest Path from a to z illustrates how Dijkstra algorithm works. Afterwards, we will show that this algorithm always produces the length of a shortest path between two vertices in a weighted graph. EXAMPLE 2 Use Dijkstra algorithm to find the length of a short

45、est path between the vertices a and z in the weighted graph displayed in Figure 4(a).Solution: The steps used by Dijkstra ' s algo rfthma shortest path between a and z are shown in Figure 4.Ateach iteration of the algorithm the vertices of the set Sk are circled.A shortest path from a to each ve

46、rtex containing only vertices in Sk is indicated for each iteration. The algorithm terminations when z is circled. We find that a shortest path from a to z is a,c,b,d,e,z with length 13.Remark: In performing Dijkstra' s algorithm it is sometimes more convenient to keep track oflabels of vertices

47、 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 path between two vertices a and zin an undirected connected weighted graph. Take as the induction hypothesis the following ass

48、ertion: At the kth 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 from a to this vertex that contain only(besides the vertex itself) vertices in S.When k = 0 , before a

49、ny iterations are carried outS = , so the length of a shortest path from a to a vertex other than a is 二.Hence, the basis, case is true.Assume that the inductive hypothesis holds for the kth iteration. Let v be the vertex added to Sat the (k 1) st iteration, so v is a vertex not in S at the end of t

50、he kth iteration with the smallest label (in the case of ties, 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 of a shortest path from a .Also, v must be labeled with the length of a shortest pa

51、th to it from a . If this were not the case, at the end of the kth iteration there would be a path of length less than L(k)(v) is the length of a shortest path from a to v containing only vertices in S after the kth iteration. Let u be the first vertex not in 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. This contradicts the choice ofv. Hence,(i) holds at the end of the (k 1)st iteration.Let u be a vertex not