最短路徑文獻(xiàn)翻譯終極版

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

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

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

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

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

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

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

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

9、最短通路的長(zhǎng)度。在算法1里給出迪克斯特拉 算法。隨后將證明這個(gè)算法的正確性。算法1迪克施特拉算法Procedure DijkkStraG:所有權(quán)都為正數(shù)的帶權(quán)連通簡(jiǎn)單圖 G帶有頂點(diǎn)a =v0,v,.= z和權(quán)wv,vj,其中假設(shè)M,vj不是G里的邊，那么wvi,vj=8For i:=1 tonLvi:=00L(a):=0S : =*黃河科技學(xué)院畢業(yè)論文(文獻(xiàn)翻譯)第6頁(yè)(現(xiàn)在初始化標(biāo)記，使得a的標(biāo)記為0而所有其余標(biāo)記為 8,S是空集合WhilezSBeginu:=不屆丁S的L(u)最小的一個(gè)頂點(diǎn)S : =SUuFor所有不屆丁S的頂點(diǎn)vIfL(u) w(u,v) : L(v)thenL(v):

10、=L(u) w(u,v)這樣就給S里添加帶最小標(biāo)記的頂點(diǎn)，而且更新不在S里的頂點(diǎn)的標(biāo)記endL(z)=從a到z的最短通路的長(zhǎng)度下面的例子說(shuō)明迪克施特拉算法是如何工作的。隨后我們將證明這個(gè)算法總是產(chǎn)生帶權(quán)圖里兩個(gè)頂點(diǎn)之間最短通路的長(zhǎng)度。例2用迪克施特拉算法求圖8-64a所示的帶權(quán)圖里頂點(diǎn)a與z之間最短通路的長(zhǎng) 度。解 圖8-64里顯示了迪克斯特拉算法求a與z之間最短通路所用的步驟。在算法的 每次迭代里，用圓圈圈起集合&里的頂點(diǎn)。對(duì)每次迭代都標(biāo)明了只包含Sk里頂點(diǎn)的從a到每個(gè)頂點(diǎn)的最短通路。當(dāng)圓圈圈到z時(shí)，算法終止。找到從a到z的最短通路是a,c,b,d,e,長(zhǎng)度為13。下一步，用歸納論證

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

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

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

14、大功告成。可以用不超過(guò)n-1次比擬來(lái)找出不在Sk里 的帶最小標(biāo)記的頂點(diǎn)。 丁是我們使用一次加法和一次比擬來(lái)更新不在Sk中的每一個(gè)頂點(diǎn) 的標(biāo)記，所以在每次迭代里的運(yùn)算不超過(guò)2(n1)次，因?yàn)樵诿看蔚镆碌臉?biāo)記不 超過(guò)n-1個(gè)。因?yàn)榈螖?shù)不超過(guò)n-1次，每次迭代的運(yùn)算次數(shù)不超過(guò)2(n1),所以 有下面的定理。定理2迪克斯特拉算法使用O(n2)次運(yùn)算(加法和比擬)來(lái)求出連通簡(jiǎn)單無(wú)向帶 權(quán)圖里兩個(gè)頂點(diǎn)之間最短通路的長(zhǎng)度。來(lái)源于：羅森(美).離散數(shù)學(xué)及其應(yīng)用.北京：機(jī)械工業(yè)出版社，2003. 8(6) : 491-496.黃河科技學(xué)院畢業(yè)論文文獻(xiàn)翻譯第9頁(yè)附:英文原文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è)論文文獻(xiàn)翻譯第10頁(yè)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è)論文文獻(xiàn)翻譯第11頁(yè)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è)論文文獻(xiàn)翻譯第12頁(yè)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è)論文文獻(xiàn)翻譯第13頁(yè)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è)論文文獻(xiàn)翻譯第14頁(yè)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è)論文(文獻(xiàn)翻譯) 第15頁(yè)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è)論文文獻(xiàn)翻譯第16頁(yè)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è)論文文獻(xiàn)翻譯第17頁(yè)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