3第三章最短路問題課件

1、第三章 最短路問題 讓我們先把最短路問題的提法明確一下3.1 什么是最短路問題 1. 求有向圖上的最短路問題：設(shè)G=(V,A)是一個(gè)有向圖，它的每一條弧ai都有一個(gè)非負(fù)的長度l(ai).在G中指定了兩個(gè)頂點(diǎn)vs與vt,要求把從vs到vt并且長度最小的有向路找出來 2. 求無向圖上的最短(無向)路問題：設(shè)G=(V,E)是一個(gè)無向圖，它的每一條弧ei都有一個(gè)非負(fù)的長度l(ei).在G中指定了兩個(gè)頂點(diǎn)vs與vt,要求把連接vs與vt并且長度最小的(無向)路找出來 上面兩個(gè)問題都可以稱為最短路問題很容易看出，這兩個(gè)問題都有著大量的生產(chǎn)實(shí)際背景.事實(shí)上，大至海、陸、空各種運(yùn)輸，小至一個(gè)人每天上班，都會(huì)遇

2、到最短路問題.正因?yàn)樗锰幋?，所以近二、三十年來國?nèi)外對(duì)這個(gè)問題進(jìn)行了不少研究，也找到了許多比較好的計(jì)算方法. 有趣的是，有些問題，從表面上看與最短路問題沒有什么關(guān)系，卻可以歸結(jié)為最短路問題.下面就來舉兩個(gè)這樣的例子： 例1 渡河問題：一個(gè)人帶了一只狼、一只羊和一棵白菜想要過河,河上有一只獨(dú)木船,每次除了人以外,只能帶一樣?xùn)|西.另外,如果人不在旁時(shí),狼就要吃羊,羊就要吃白菜.問應(yīng)該怎樣安排渡河,才能做到把所有東西都帶過河去,而且在河上來回的次數(shù)又最少. 當(dāng)然，這個(gè)問題不用圖論也能解決大家一眼就能看出，第一次應(yīng)該帶著羊過河，讓狼和白菜留下,以下怎么渡法呢？ 下面就來講一下怎樣把這個(gè)問題轉(zhuǎn)化成最短

3、路問題 我們用M代表人，W代表狼，S代表羊，V代表白菜.開始時(shí)，設(shè)人和其他三樣?xùn)|西都在河的左岸，這種情況，我們用MWSV來表示.又例如人帶了羊渡到河的右岸去了，這時(shí)左岸留下了狼和白菜，這種情況就用WV來表示.例如MWS表示人(M)狼(W)羊(S)在左岸而白菜(V)在右岸這種情況.那么總共可能有幾種允許的情況呢 如果不管狼是否吃羊、羊是否吃白菜，那么總共有16中情況，它們分別是：MWSV, MWS, MWV, MSV, WSV, MW, MS, MV , WS, WV, SV, M, W, S, V, (空集) 例如MS表示人和羊在左岸，而狼和白菜在右岸；表示左岸是空集，即人、狼、羊、白菜都已渡

4、到右岸去了.檢查一下就可以知道，這16種情況中有6種情況是不允許出現(xiàn)的.分別是：WSV, MW, MV, WS, SV, M.例如WSV表示狼、羊、白菜都在左岸而人在右岸，因?yàn)槿瞬辉谂赃吙粗?狼就要吃羊，羊也要吃白菜；又如MV表示人和白菜在左岸，而狼和羊在右岸，當(dāng)然也是不行的.因此，允許出現(xiàn)的情況只有10種. 現(xiàn)在我們就來構(gòu)造一個(gè)圖G，它的頂點(diǎn)就是這10種情況，G中的邊是按照下述原則來連的；如果情況甲經(jīng)過一次渡河可以變成情況乙，那么就在情況甲與乙之間連一條邊.WVWSVMWSMWVWSVMSMWSV 例如，MWSV經(jīng)過一次渡河可以變成WV(人帶著羊過河，左岸留下狼和白菜)，又例如MWV經(jīng)過一次

5、渡河可以變?yōu)閃(人帶著白菜過河，留下狼)，或變?yōu)閂.當(dāng)然反過來，W也可以變?yōu)镸WV(人帶著白菜從右岸返回左岸). 作出了圖G以后，渡河問題就歸結(jié)為下述問題了：“在圖G中找一條連接頂點(diǎn)MWSV與，并且包含邊數(shù)最少的路”.如果我們?cè)O(shè)G的每條邊的長度都是1，那么也可以把渡河問題歸結(jié)為：“找一條連接MWSV與的最短路”.例2: 某兩人有一只8升的酒壺裝滿了酒，還有兩只空壺，分別為5升和3升.現(xiàn)要將酒平分，求最少的操作次數(shù).解 設(shè)x1,x2,x3分別表示8,5,3升酒壺中的酒量.則容易算出(x1,x2,x3) 的組合形式共24種.(0,5,3);(1,5,2);(1,4,3);(2,5,1);(2,4,

6、2);(2,3,3); (3,5,0);(3,4,1);(3,3,2);(3,2,3);(4,4,0);(4,3,1);(4,2,2);(4,1,3);(5,3,0);(5,2,1);(5,1,2);(5,0,3);(6,2,0);(6,1,1);(6,0,2);(7,1,0);(7,0,1);(8,0,0);于是問題轉(zhuǎn)化為在該圖中求 (8,0,0)到(4,4,0)的一條最短路(求最短路的算法在有向圖中仍適用).結(jié)果如下： 每種組合用一個(gè)點(diǎn)表示，若點(diǎn)u能通過倒酒的方式變換為v,則 u向v 連有向邊，并將各邊賦權(quán)1，得一個(gè)有向賦權(quán)圖. 大家也許會(huì)認(rèn)為，這兩個(gè)例子本來就不很難，把它轉(zhuǎn)化成圖論問題，

7、倒相當(dāng)麻煩，有什么好處呢？其實(shí)這種做法還是很有好處的.因?yàn)樵谵D(zhuǎn)化前，想解決這些問題，只能用湊的辦法，或者最多是憑經(jīng)驗(yàn).而轉(zhuǎn)化成圖論問題以后，就可以用一種系統(tǒng)的方法解決了. 最后，還要指出一下，求最短有向路和求最短無向路這兩個(gè)問題是密切關(guān)聯(lián)的.下面將看到，求最短有向路的計(jì)算方法也可以用來求最短無向路. 在這一章中，我們假設(shè)遇到的圖G都是簡(jiǎn)單圖.這樣假設(shè)是合理的，因?yàn)槿绻鸊有平行弧或平行邊，例如有好幾條從vi到vj的弧，那么很顯然，可以把這些弧中最短的一條留下，其余的都去掉，然后在剩下的簡(jiǎn)單圖上再來求從vs到vt的最短有向路.因?yàn)镚是簡(jiǎn)單圖，所以每一條弧ak被它的起點(diǎn)vi與終點(diǎn)vj唯一決定，因此，

8、下面我們就用或來表示一條弧，用(vi,vj)或(i,j)來表示邊，而用l(i,j)來表示弧或邊的長度. 這一節(jié)介紹一種求有向圖上最短有向路的方法，叫做標(biāo)號(hào)法。3.2 求最短有向路的標(biāo)號(hào)法 所謂標(biāo)號(hào),我們是指與圖的每一個(gè)頂點(diǎn)對(duì)應(yīng)的一個(gè)數(shù)(或幾個(gè)數(shù))例如設(shè)G=(V,A)的頂點(diǎn)集合是V=v1,v2, ,vn，如果我們能使v1對(duì)應(yīng)一個(gè)數(shù)b(1)，v2對(duì)應(yīng)數(shù)b(2)，vn對(duì)應(yīng)數(shù)b(n)，那么，這些數(shù)b(i)就稱為vi的標(biāo)號(hào)，當(dāng)然，在不同的問題中，標(biāo)號(hào)b(i)一般代表不同的意義. 回到我們要解決的最短有向路問題上來.為確定起見，我們?cè)O(shè)vs=v1，vt=vn,也就是說我們要找的是從v1到vn的最短有向路.下

9、面介紹的方法可以把從v1到G的每一個(gè)頂點(diǎn)vj的最短有向路都求出來(或者指出不存在從v1到vj的有向路，即v1不可達(dá)vj) 我們把整個(gè)計(jì)算分成若干“輪”來進(jìn)行(一個(gè)“輪”就是一個(gè)大步)，每一輪中，將求出v1到某一個(gè)頂點(diǎn)vj的最短路以及這條最短路的長度b(j).我們把b(j)就叫做頂點(diǎn)vj的標(biāo)號(hào).再強(qiáng)調(diào)一下，頂點(diǎn)vj的標(biāo)號(hào)代表的是從v1到vj的最短路的長度.另外，如果說“頂點(diǎn)vj已經(jīng)有標(biāo)號(hào)了”或“vj是已標(biāo)號(hào)點(diǎn)”，就意味著從v1到vj的最短路以及這條最短路的長度都已經(jīng)求出來了. 計(jì)算開始時(shí)，令b(1)=0，v1變?yōu)橐褬?biāo)號(hào)點(diǎn)，其余頂點(diǎn)都是未標(biāo)號(hào)點(diǎn).這樣做的意義很清楚，因?yàn)閎(1)代表從v1到v1的最

10、短路的長度，當(dāng)然不用計(jì)算就可以知道，它應(yīng)該等于0. 如果計(jì)算是在一張圖上進(jìn)行，那么我們可以在頂點(diǎn)v1旁邊寫一個(gè)數(shù)0，表示這是v1的標(biāo)號(hào)并且已算出. 每一輪計(jì)算可以分成下面幾個(gè)步驟. 步驟1 找出所具有下述性質(zhì)的?。浩瘘c(diǎn)vi是已標(biāo)號(hào)點(diǎn)而終點(diǎn)vj是未標(biāo)號(hào)點(diǎn).如果這樣的弧不存在，計(jì)算結(jié)束. 步驟2 對(duì)于步驟1中找到的每一條弧，計(jì)算一個(gè)數(shù)：k=b(i)+l. (如果這個(gè)k在前面各輪計(jì)算中已經(jīng)算過，就不必再算)也就是說：k等于弧的起點(diǎn)的 標(biāo)號(hào)加上弧的長度.把算出的k的值就寫在弧的旁邊，并在數(shù)的外面加上一個(gè)方括號(hào)然后找出使k最小的弧(如果有好幾條弧都使k達(dá)到最小，可任取一條) 步驟3 把弧畫成粗線，把頂點(diǎn)

11、vd變?yōu)橐褬?biāo)號(hào)點(diǎn)，令vd的標(biāo)號(hào)b(d)就等于k.這一輪計(jì)算結(jié)束. 在一輪計(jì)算結(jié)束后，應(yīng)該檢查一下，是不是所有頂點(diǎn)都得到標(biāo)號(hào)了，如果是的，那么整個(gè)計(jì)算就結(jié)束了；如果不是，即還有未標(biāo)號(hào)的頂點(diǎn)，就轉(zhuǎn)向下一輪計(jì)算(即再從步驟1開始計(jì)算). 如果我們要求從vs到vt的最短路，只要vt得到標(biāo)號(hào)，計(jì)算就結(jié)束了，從而可以省去一些計(jì)算. 如果在計(jì)算結(jié)束時(shí)，還有一些點(diǎn)沒有得到標(biāo)號(hào)，那么可以肯定，從起點(diǎn)到這些點(diǎn)的有向路是不存在的. 該計(jì)算方法的框式圖如下：開始：令b(1)=0，v1為已標(biāo)號(hào)點(diǎn)求所有起點(diǎn)已標(biāo)號(hào)、終點(diǎn)未標(biāo)號(hào)的弧的集合B，B是不是空集合？對(duì)于B中的每一條弧，計(jì)算，k=b(i)+l,求出使k最小的弧.將弧加

12、粗，令b(d)=k,vd成為已標(biāo)號(hào)點(diǎn)是否還有未標(biāo)號(hào)的頂點(diǎn)計(jì)算結(jié)束是否是 現(xiàn)在來討論標(biāo)號(hào)法好不好？要回答這個(gè)問題,首先應(yīng)該明確一下什么叫“好”,什么叫“不好”一般說來，主要的好壞標(biāo)準(zhǔn)是計(jì)算起來快不快不快(還有比的標(biāo)準(zhǔn)，例如容不容易拿上計(jì)算機(jī)計(jì)算；是否易于普及等等)，或者說，用這個(gè)方法計(jì)算時(shí)，需要進(jìn)行的運(yùn)算次數(shù)多不多.當(dāng)然，運(yùn)算次數(shù)越少越好.3.3 標(biāo)號(hào)法好不好 大家也許會(huì)說，運(yùn)算次數(shù)多少不完全決定于采用什么方法，還和要解決的問題有關(guān)同樣用標(biāo)號(hào)法，解一個(gè)只有10個(gè)頂點(diǎn)的問題可能只要進(jìn)行幾千次運(yùn)算，而解一個(gè)100個(gè)頂點(diǎn)的問題，就可能要進(jìn)行幾百萬次運(yùn)算了，這又怎么比較呢？ 辦法還是有的.那就是，設(shè)圖G

13、有n個(gè)頂點(diǎn)(為了簡(jiǎn)單起見，我們就不研究邊數(shù)m的影響了),我們來估計(jì)一下，把標(biāo)號(hào)法用到圖G上去需要進(jìn)行幾次運(yùn)算.當(dāng)然，這樣估計(jì)出來的結(jié)果不會(huì)是一個(gè)確定的數(shù),而是象n2,3n3+4n2,2n等等這樣的與n有關(guān)的數(shù),即n的函數(shù).然后再以這種函數(shù)為標(biāo)準(zhǔn)來比較方法的好壞.比如說，有兩種方法，第一種要進(jìn)行n3次加法，而第二種要進(jìn)行n5次加法，當(dāng)然第一種就比第二種好，因?yàn)樵趎較大時(shí)，n5比n3要大多了. 上面講的是怎樣比較兩種方法誰好誰壞.現(xiàn)在總共只講了一個(gè)標(biāo)號(hào)法，又怎么評(píng)論它的好壞呢？也有辦法的.目前一般認(rèn)為，如果一種方法所需要的運(yùn)算次數(shù)能表示成n的多項(xiàng)式，例如n4,2n2+3n等等.這種方法就認(rèn)為是好的

14、，或者說是有效的.而如果一種方法的計(jì)算次數(shù)是某一個(gè)數(shù)的n次冪，例如2n,10n，即是n的指數(shù)函數(shù)，這種方法就認(rèn)為是不好的，或者說是無效的.請(qǐng)看如下這張表：n5102030501001000方法A(運(yùn)算次數(shù)n3)6251000800027000625000106109方法B(運(yùn)算次數(shù)2n)3210241061091015103010300上表中對(duì)一種需要進(jìn)行n3次運(yùn)算的方法A與另一種需要進(jìn)行2n次運(yùn)算的方法B進(jìn)行了比較(關(guān)于2n的近似值,我們是以210=1024103來估算的,例如250=(210)5(103)5=1015).從上表可以看出，方法B的運(yùn)算次數(shù)的增長速度是驚人的.也許有的人會(huì)認(rèn)為，

15、現(xiàn)在反正有大型計(jì)算機(jī)，計(jì)算次數(shù)多一些無所謂.其實(shí)不然.例如我們有一個(gè)每秒能計(jì)算一百萬次的計(jì)算機(jī)，那么，在1000秒內(nèi)可以進(jìn)行10001000000=109次(即十億次)運(yùn)算,如果用方法A,則則可以解決一個(gè)1000個(gè)頂點(diǎn)的問題，而用方法B呢？卻只能解決一個(gè)30個(gè)頂點(diǎn)的問題.如果想用方法B來解決一個(gè)100個(gè)頂點(diǎn)的問題，即使用的是每秒能計(jì)算一億次的計(jì)算機(jī)，也需要1022秒，即要好幾萬億年. 從上面的簡(jiǎn)單比較久可以看出，為什么說計(jì)算次數(shù)是n的多項(xiàng)式的方法是有效的，而計(jì)算次數(shù)是n的指數(shù)函數(shù)的方法是無效的.另外，也可以看出，單靠提高計(jì)算機(jī)的速度還不夠，還必須從數(shù)學(xué)上尋求有效的計(jì)算方法. 現(xiàn)在再回過頭來看看

16、標(biāo)號(hào)法好不好.回想一下標(biāo)號(hào)法的各輪計(jì)算，可以看出，它只包含兩種運(yùn)算：加法與比較大小(比較大小也需要花費(fèi)時(shí)間，所以也要考慮).加法用于計(jì)算k(i,j)，每計(jì)算一個(gè)k(i,j)進(jìn)行一次加法，而且每一條弧最多只計(jì)算一次.因此,如果圖中有m條弧，那么至多進(jìn)行m次加法.對(duì)于一個(gè)有n個(gè)頂點(diǎn)的簡(jiǎn)單有向圖來說，最多有n(n-1)條弧(假設(shè)從每一個(gè)頂點(diǎn)vi出發(fā)，都有n-1條弧指向其他的n-1個(gè)頂點(diǎn))，因此，最多進(jìn)行n(n-1)次加法，放寬一點(diǎn)，也可以說，至多進(jìn)行n2次加法. 另外，在每一輪計(jì)算中，在找使k(i,j)達(dá)到最小的弧時(shí)，要用到比較大小的運(yùn)算，一般說來，要從s個(gè)數(shù)中把最小的數(shù)找出來，要進(jìn)行s-1次比較(

17、例如有四個(gè)數(shù)a1,a2,a3,a4，那么可以先拿a1與a2比，然后拿這兩個(gè)數(shù)中小的數(shù)與a3比，再拿小的數(shù)與a4比，比三次就能知道哪個(gè)數(shù)最小了).那么在每一輪的步驟1中，一般會(huì)選出幾條弧呢？算得寬一些，至多n2條吧(事實(shí)上要少得多)，因此至多進(jìn)行n2次比較，整個(gè)計(jì)算的輪數(shù)不會(huì)超過n，因此，總起來說，至多進(jìn)行n3次比較大小的運(yùn)算. 通過上面的估計(jì)，可以得出這樣的結(jié)論：把標(biāo)號(hào)法用在一個(gè)n個(gè)頂點(diǎn)的圖上，至多進(jìn)行n2次加法和n3次比較大小.因此，可以說，標(biāo)號(hào)法是一種好的、有效的計(jì)算方法.問題：給定簡(jiǎn)單權(quán)圖G = (V, E)，并設(shè)G 有n個(gè)頂點(diǎn)，求G中點(diǎn)u0到其它各點(diǎn)的最短路.Dijkstra算法 (E

18、dmonds, 1965)(2) 若i = n-1，則停；否則令 = V Si , 對(duì)每個(gè)v ，令 l(v) = min l(v)，l(ui) + w(uiv)(1) 置 l(u0) = 0；對(duì)所有vV u0，令 l(v) = ； S0 = u0，i = 0.3.4 求無向圖上的最短路的方法并用 ui+1記達(dá)到最小值的某點(diǎn).置S i+1= Siu i+1，i = i+1（表示賦值語句，以后的算法中相同），轉(zhuǎn)（2）.終止后，u0 到 v 的距離由 l(v) 的終值給出.)(minvliSv(3) 計(jì)算說明： （1） 算法中w(uiv) 表示邊 uiv 的權(quán)； （2） 若只想確定u0到某頂點(diǎn)v0的

19、距離， 則當(dāng)某 uj 等于 v0 時(shí)即停；（3） 算法稍加改進(jìn)可同時(shí)得出u0到其它點(diǎn)的最短路.例3 求圖 G 中 u0 到其它點(diǎn)的距離.u0 742155813G :解 u0 742155813 （a）初始標(biāo)號(hào)u0 742155813 2 4 7（b）用與u0關(guān)聯(lián)的邊的權(quán)2,4,7分別更新與u0相鄰的三個(gè)點(diǎn)的標(biāo)號(hào);（c）取小圓點(diǎn)中標(biāo)號(hào)最小者得 u1； u0 742155813 2 4 7u1 （d）對(duì)與u1相鄰的小圓點(diǎn)，用 l (u1) + w (u1v) = 2+1 = 3更新標(biāo)號(hào)4； 2+5=7 更新兩個(gè)；u0 742155813 2 7 37 7u1 （e）取小圓點(diǎn)中標(biāo)號(hào) 最小者得 u2

20、.u0 742155813 2 7 37 7u1 u2 u4 u0 742155813 2 7 34 6（h）u1 u2 0u3u5 u0 742155813 2 7 37 7u1 u2 4 （f）u0 742155813 2 7 3 6u1 u2 （g）u0 742155813 2 7 34 6u1 u2 u33.5 圖的距離表 在生產(chǎn)實(shí)踐中，往往需要求出一個(gè)圖的任意兩個(gè)頂點(diǎn)之間的最短路.例如，一個(gè)鐵路局在編制他所屬的各個(gè)車站之間的運(yùn)輸里程表時(shí)，就會(huì)遇到這類問題另外，對(duì)于不少圖論中的極值問題，往往在計(jì)算前首先必須把圖中任意兩個(gè)頂點(diǎn)之間的最短路及最短路的長度都求出來. 要把一個(gè)圖的任意兩個(gè)頂點(diǎn)

21、之間的最短路都求出來,并不困難.例如,在有向圖上,用前面講的方法,計(jì)算一次就可以把從v1到所有頂點(diǎn)的有向路都求出來了,接著從v2出發(fā)，就是一開始令v2為已標(biāo)號(hào)點(diǎn)，并且令v2的標(biāo)號(hào)b(2)=0，又可以把從v2到其它各點(diǎn)的最短路求出來，這樣連續(xù)算n次，就可以把從任意一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路都求出來了.對(duì)于無向圖也可以用相似的方法來解決 以下圖為例：這個(gè)圖有6個(gè)頂點(diǎn)，在圖3.5.2的(a)到(f)中分別畫了以為起點(diǎn)的計(jì)算結(jié)果.v12v3v2v4v5v63853444376圖3.5.1v12v3v2v4v5v61030367102158(a)起點(diǎn)v18107圖3.5.2v15v3v2v4v5v61

22、145480126(b)起點(diǎn)v26118圖3.5.2v124v3v2v4v5v61523242319719(c)起點(diǎn)v30715圖3.5.2v113v3v2v4v5v670134878(d)起點(diǎn)v4774圖3.5.2v19v3v2v4v5v63898434(e)起點(diǎn)v5330圖3.5.2v117v3v2v4v5v68161716121112(f)起點(diǎn)v61108圖3.5.2 為方便起見，今后我們把從頂點(diǎn)vi到vj的最短路的長度叫做vi到vj的距離，記作d(vi,vj)或d(i,j) 從上面的六張圖雖然可以查出任意一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離，但是這樣畢竟不太方便.比較方便的辦法是把這些距離集中寫

23、在一張象如下的表上在這張表上，橫著排的一行數(shù)字叫做“行”，豎著排的一列數(shù)字叫做“列”.在表中的第1行上，寫的是從v1到各個(gè)頂點(diǎn)的距離，同樣第2行是v2到各頂點(diǎn)的距離，.而第1列則是從各個(gè)頂點(diǎn)到v1的距離，其余各列也一樣.v1v2v3v4v5v6v10283710v25064811v32419023157v41387047v5943803v61712111680 如上這樣的表格叫做圖G的距離表，從表上查頂點(diǎn)vi到頂點(diǎn)vj的距離要比從前面的六張圖上查容易得多了1.2.3 每對(duì)頂點(diǎn)之間的最短路 求每對(duì)頂點(diǎn)之間最短路的算法是Floyd算法:1.算法的基本思路: 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法

24、依次構(gòu)造出p個(gè)矩陣D(1),D(2), ,D(p),使最后得到的矩陣D(p)成為圖的距離矩陣,同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑.2.算法原理:(1)求距離矩陣的方法:把帶權(quán)鄰接矩陣W作為距離矩陣的初值,即: D(0)=(dij(0)pp=W10 D(1)=(dij(1) pp,其中dij(1)=mindij(0),di1(0)+d1j(0),dij(1)是從vi到vj的只允許以v1作為中間點(diǎn)的路徑中最短路的長度.20 D(2)=(dij(2) pp,其中dij(2)=mindij(1),di2(1)+d1j(1),dij(2),是從vi到vj的只允許以v1,v2作為中間點(diǎn)的路徑中最

25、短路的長度. P0 D(p)=(dij(p) pp,其中dij(p)=mindij(p-1),dip(p-1)+dpj(p-1),dij(p)是從vi到vj的只允許以v1,v2, ,vp作為中間點(diǎn)的路徑中最短路的長度.即是從vi到vj中間可插入任何頂點(diǎn)的路徑中最短路的長度,因此:D(P)即是距離矩陣.(2)求路由矩陣的方法: 在建立距離矩陣的同時(shí)可建立路由矩陣R,R=(rij) pp,rij的含義是從vi到vj的最短路要經(jīng)過點(diǎn)號(hào)為rij的點(diǎn). R(0)=(rij(0) pp,rij(0)=j每求得一個(gè)D(k)時(shí),按下列方式產(chǎn)生相應(yīng)的新的R(k): rij(k)= 即當(dāng)vk被插入任何兩點(diǎn)間的最短

26、路徑時(shí),被記錄在R(k)中,依次求D(p)時(shí)求得R(p),可由R(p)來查找任何點(diǎn)對(duì)之間最短路的路由.(3)查找最短路路由的方法: 若rij(p)=p1,則點(diǎn)p1是點(diǎn)i到j(luò)點(diǎn)的最短路的中間點(diǎn),然后用同樣的方法再分頭查找,若:向點(diǎn)i追溯得:向點(diǎn)j追溯得:則由點(diǎn)i到j(luò)的最短路的路由為:i,pk, ,p2,p1,q1,q2, ,qm,j3.算法步驟:Floyd算法:求任意兩點(diǎn)間的最短路:D(i,j):i到j(luò)的距離;R(i,j):i到j(luò)的插入點(diǎn).輸入帶權(quán)鄰接矩陣W(i,j),(1)賦初值;對(duì)所有i,j: d(i,j)W(i,j),r(i,j)j,k1(2)更新d(i,j), r(i,j) :對(duì)所有i,

27、j,若: d(i,k)+ d(k,j)d(i,j)則: d(i,j) d(i,k)+d(k,j), r(i,j) k (3)若k=p,停止;否則:k k+1,轉(zhuǎn)(2).下面給一個(gè)程序：Floyd-Warshall算法Input:非負(fù)元素的nn矩陣cijOutput: nn矩陣dij ，其中dij是在弧權(quán)為cij下，自i到j(luò)的最短路長度。Begin for all ij do dij:=cij; for i=1, ,n do dij:=; for j=1, ,n do for i=1, ,n ij do for k=1, ,n kj do dik:=mindik,dij+djkend例3:求下面

28、加權(quán)圖的任意兩點(diǎn)間的距離與路徑.解:v1v2v3v4v5932247插入v1得:矩陣中帶下劃線的元素為經(jīng)迭代比較以后有變化的元素,即需要引入中間點(diǎn)v1,從而R(1)中相應(yīng)的位置換為1.插入v2得:插入v3得:插入v4得:插入v5得:D(5)=D(4),R(5)=R(4) 從D(5)中得各頂點(diǎn)間的最短路,從R(5)中可追溯出最短路的路由.例如:從D(5)中得d51(5) =9,故從v5到v1的最短路為9,從R(5)中得r51(5)=4.由v4向v5追溯: r54(5)=3, r53(5)=3;由v4向v1追溯: r41(5)=1.所以:從v5到v1的最短路徑為:5341.應(yīng)用：可化為最短路問題的多階段決策問題: 對(duì)于最優(yōu)化問題中的多階段決策問題,?？捎脛?dòng)態(tài)規(guī)劃來處理,它的特點(diǎn)是先將一個(gè)復(fù)雜的問題分解成相互聯(lián)系的若干個(gè)階段,每個(gè)階