圖論4最短路問題ppt課件

1、1返回 結(jié)束第七章 圖論引言引言7.1 圖的基本概念圖的基本概念7.2 路與連通路與連通7.3 圖的矩陣表示圖的矩陣表示7.4 最短路徑問題最短路徑問題7.5 圖的匹配圖的匹配8.1 Euler圖和圖和Hamilton圖圖8.2 樹樹8.3 生成樹生成樹 8.4 平面圖平面圖2返回 結(jié)束7.4 最短路問題v一、問題的提出一、問題的提出v )(G賦權(quán)圖網(wǎng)絡(luò)）：賦權(quán)圖網(wǎng)絡(luò)）： G=(V, E) 中，給每條邊中，給每條邊 a= 賦予一個非負(fù)實(shí)數(shù)權(quán)賦予一個非負(fù)實(shí)數(shù)權(quán) wij ，得到一個有向網(wǎng)絡(luò)，得到一個有向網(wǎng)絡(luò)3返回 結(jié)束7.4 最短路問題v途徑v路徑長度 v非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。v

2、帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和距離矩陣距離矩陣 對上述網(wǎng)絡(luò)，定義對上述網(wǎng)絡(luò)，定義 D=(dij)nn，n=|V| wij 當(dāng)當(dāng) E dij = 其它其它帶權(quán)路徑長度帶權(quán)路徑長度 對上述網(wǎng)絡(luò)，途徑對上述網(wǎng)絡(luò)，途徑 v1, v2 , ,vk 的帶權(quán)路徑長度定義為的帶權(quán)路徑長度定義為1,11ki iidw4返回 結(jié)束7.4 最短路問題最短路問題在實(shí)際工作中應(yīng)用最短路問題在實(shí)際工作中應(yīng)用1、通訊網(wǎng)絡(luò)中最可靠問題、通訊網(wǎng)絡(luò)中最可靠問題2、最大容量問題、最大容量問題3、統(tǒng)籌方法中求關(guān)鍵路線、統(tǒng)籌方法中求關(guān)鍵路線4、背包問題、背包問題5、選址問題、選址問題6、工件加工順序問題、工件加工順序問題7、中

3、國郵遞員問題、中國郵遞員問題背包問題背包問題(Knapsack problem)是一種組合優(yōu)化的是一種組合優(yōu)化的NP完全問題。完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)問題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。中。5返回 結(jié)束7.4 最短路問題v例一位旅客要從一位旅客要從A城到城到B城城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選

4、擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中所花時間最短的路線；他希望選擇一條途中所花時間最短的路線；他希望選擇一條途中費(fèi)用最小的路線；他希望選擇一條途中費(fèi)用最小的路線；v5v4v3v2v1v0 100 6030101020 5 50這些問題均是帶權(quán)圖上的最短路徑問題。這些問題均是帶權(quán)圖上的最短路徑問題。邊上的權(quán)表示一站邊上的權(quán)表示一站邊上的權(quán)代表距離邊上的權(quán)代表距離邊的權(quán)代表費(fèi)用邊的權(quán)代表費(fèi)用 6返回 結(jié)束7.4 最短路問題vDijkstra算法vFloyd算法vFloyd-Warshall算法7返回 結(jié)束7.4 最短路問題vDijkstra算法算法 Dijkstra算法是由荷蘭計(jì)算機(jī)科

5、學(xué)家狄克斯特拉算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉Dijkstra于于1959 年提出的，因此又叫狄克斯特拉算法。年提出的，因此又叫狄克斯特拉算法。是從一個頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向是從一個頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問題。圖中最短路徑問題。 荷蘭計(jì)算機(jī)科學(xué)教授荷蘭計(jì)算機(jī)科學(xué)教授Edsger W.Dijkstra(1930-) 在在1972年年獲得美國計(jì)算機(jī)協(xié)會授予的圖靈獎，這是計(jì)算機(jī)科學(xué)中最具獲得美國計(jì)算機(jī)協(xié)會授予的圖靈獎，這是計(jì)算機(jī)科學(xué)中最具聲望的獎項(xiàng)之一。聲望的獎項(xiàng)之一。 Dijkstra算法是求出一個連通加權(quán)簡單圖中從結(jié)點(diǎn)算法是求出一個連通加

6、權(quán)簡單圖中從結(jié)點(diǎn)a到結(jié)到結(jié)點(diǎn)點(diǎn)z的最短路。邊的最短路。邊(i,j)的權(quán)的權(quán)(i,j)0，且結(jié)點(diǎn)，且結(jié)點(diǎn)x的標(biāo)號為的標(biāo)號為L(x)。結(jié)束時，結(jié)束時，L(z)是從是從a到到z的最短長度。的最短長度。 舉例來說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表舉例來說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示城市間開車行經(jīng)的距離。示城市間開車行經(jīng)的距離。 Dijkstra算法可以用來找到兩個算法可以用來找到兩個城市之間的最短路徑。城市之間的最短路徑。 8返回 結(jié)束7.4 .1 Dijkstra算法Dijkstra算法基本思想:把圖中所有結(jié)點(diǎn)分為兩組，每一個結(jié)點(diǎn)對應(yīng)一個距離值。第一組：包括已確定最短路徑的結(jié)點(diǎn)，

7、結(jié)點(diǎn)對應(yīng)的距離值是由v0到此結(jié)點(diǎn)的最短路徑長度； 第二組：包括尚未確定最短路徑的結(jié)點(diǎn)，結(jié)點(diǎn)對應(yīng)的距離值是v0經(jīng)由第一組結(jié)點(diǎn)中間結(jié)點(diǎn)至此結(jié)點(diǎn)的最短路徑長度。 按最短路徑長度遞增的順序把第二組的結(jié)點(diǎn)加到第一組中去，直至v0可達(dá)的所有結(jié)點(diǎn)都包含于第一組。在這個過程中，總保持從v0到第一組各結(jié)點(diǎn)的最短路徑長度都不大于從v0至第二組任何結(jié)點(diǎn)的路徑長度。9返回 結(jié)束 7.4 .1 Dijkstra算法設(shè)源點(diǎn)為v0初始時v0進(jìn)入第一組，v0的距離值為0；第二組包含其它所有結(jié)點(diǎn)，這些結(jié)點(diǎn)對應(yīng)的距離值這樣確定設(shè)vi為第二組中的結(jié)點(diǎn)） 然后每次從第二組的結(jié)點(diǎn)中選一個其距離值為最小的結(jié)點(diǎn)vm加到第一組中。每往第一組

8、加入一個結(jié)點(diǎn)vm，就要對第二組的各結(jié)點(diǎn)的距離值作一次修正設(shè)vi為第二組的結(jié)點(diǎn)）：若加進(jìn)vm做中間結(jié)點(diǎn)使得v0至vi的路徑長度更短即vi的距離值vm的距離值+Wmi），則要修改vi的距離vi的距離值vm的距離值+Wmi）。修改后再選距離值最小的一個結(jié)點(diǎn)加入到第一組中，。 如此進(jìn)行下去，直至第一組囊括圖的所有結(jié)點(diǎn)或再無可加入第一組的結(jié)點(diǎn)存在。顯然，這種從第二組的結(jié)點(diǎn)中選距離值最小的結(jié)點(diǎn)擴(kuò)展是一種貪心策略。EvvEvvwdistiiii),(),(00010返回 結(jié)束7.4 .1 Dijkstra算法procedure Dijkstra(G:所有權(quán)都為正數(shù)的加權(quán)連通簡單圖所有權(quán)都為正數(shù)的加權(quán)連通簡單

9、圖)G帶有頂點(diǎn)帶有頂點(diǎn)av0,v1,vnz和權(quán)和權(quán)(vi,vj)，假設(shè)，假設(shè)(vi,vj)不是不是G的邊，則的邊，則(vi,vj)for i:1 to nL(vi)L(a):0S: （初始化標(biāo)記，（初始化標(biāo)記，a的標(biāo)記為的標(biāo)記為0，其余結(jié)點(diǎn)標(biāo)記為，其余結(jié)點(diǎn)標(biāo)記為，S是空集是空集while z S beginu:不屬于不屬于S的的L(u)最小的一個頂點(diǎn)最小的一個頂點(diǎn)S:Su for 所有不屬于所有不屬于S的頂點(diǎn)的頂點(diǎn)v if L(u)(u,v)L(v) then L(v):L(u)(u,v) 這樣就給這樣就給S中添加帶最小標(biāo)記的頂點(diǎn)并且更新不在中添加帶最小標(biāo)記的頂點(diǎn)并且更新不在S中的頂點(diǎn)的標(biāo)記中

10、的頂點(diǎn)的標(biāo)記 endL(z)從從a到到z的最短長度的最短長度 dij11返回 結(jié)束7.4 .1 Dijkstra算法v下面給出該算法的框圖：下面給出該算法的框圖：2( , )()f p qp通過框圖，容易計(jì)算該算法計(jì)算量通過框圖，容易計(jì)算該算法計(jì)算量 。12返回 結(jié)束7.4 .1 Dijkstra算法下面通過一個實(shí)例來說明Dijkstra算法是如何工作的。13返回 結(jié)束7.4 .1 Dijkstra算法14返回 結(jié)束7.4 .1 Dijkstra算法v 0次迭代 L(a)0L(b)L(c)L(d)L(e)L(z)S1次迭代ua，SaL(a)(a,b)044L(b)L(a)(a,c)022L(c

11、)L(a)(a,d)0L(a)(a,e)0L(a)(a,z)0L(b)4，L(c)2，L(d)L(e)L(z)2次迭代uc，Sa,cL(c)(c,b)213L(b)L(c)(c,d)2810L(d)L(c)(c,e)21012L(e)L(c)(c,z)2L(b)3，L(d)10，L(e)12，L(z)3次迭代ub，Sa,c,bL(b)(b,d)358L(d)L(b)(b,e)3145623108abcdez用Dijkstra算法求a和z之間最短路所用的步驟。 L(b)(b,z)3L(d)8，L(e)12，L(z)4次迭代ud，Sa,c,b,dL(d)(d,e)8210L(e)L(d)(d,z)

12、8614L(z)L(e)10，L(z)145次迭代ue，Sa,c,b,d,eL(e)(e,z)10313L(z)L(z)13結(jié) 束uz，Sa,c,b,d,e,z從a到z的最短路的長度為13。15返回 結(jié)束7.4 .1 Dijkstra算法vDijkstra算法算法(另外一種說明另外一種說明) 求有向網(wǎng)絡(luò)求有向網(wǎng)絡(luò) G=(V, A) 中結(jié)點(diǎn)中結(jié)點(diǎn)v1 到其它結(jié)點(diǎn)的最短距離。到其它結(jié)點(diǎn)的最短距離。 設(shè)設(shè)D為為G的距離矩陣，的距離矩陣，n=|V|，向量，向量U=(u1, u2, , un)的的ui 標(biāo)記結(jié)點(diǎn)標(biāo)記結(jié)點(diǎn)v1到到vi 的距離。的距離。 S為已取得最短路的結(jié)點(diǎn)集合，其中每個結(jié)點(diǎn)在為已取得最短

13、路的結(jié)點(diǎn)集合，其中每個結(jié)點(diǎn)在U中有中有固定標(biāo)號標(biāo)記取得的最短路的長度；固定標(biāo)號標(biāo)記取得的最短路的長度；S為未取得最短路的為未取得最短路的結(jié)點(diǎn)集合，其中每個結(jié)點(diǎn)在結(jié)點(diǎn)集合，其中每個結(jié)點(diǎn)在U中有臨時標(biāo)號。中有臨時標(biāo)號。16返回 結(jié)束7.4 .1 Dijkstra算法0. 初始化：初始化：u1(1) 0，uj(1) d1j ( j =2,3,n) S(1) v1，S(1) v2 , v3 , , vn，m=1;1. 選固定標(biāo)號：在選固定標(biāo)號：在S(m)中求中求vk，使得，使得 uk(m) =minuj(m) | vjS(m)。 假設(shè)假設(shè) uk(m) =，則，則S(m)中的結(jié)點(diǎn)中的結(jié)點(diǎn)無最短路徑；否則

14、轉(zhuǎn)無最短路徑；否則轉(zhuǎn)2。2. 判結(jié)束：令判結(jié)束：令 S(m+1) S(m) vk, S(m+1) S(m) vk 假設(shè)假設(shè) m = n1，終了。，終了。3. 修改臨時標(biāo)號：對所有修改臨時標(biāo)號：對所有vjS(m+1) ，令，令 uj(m+1) =minuj(m) , uk(m)+dkj，m m+1；轉(zhuǎn)；轉(zhuǎn)1。17返回 結(jié)束7.4 .1 Dijkstra算法vDijkstra算法只求出圖中一個特定的頂點(diǎn)到其他各定點(diǎn)的最短路。但在許多實(shí)際問題中，需求出任意兩點(diǎn)之間的最短路，如全國各城市之間最短的航線，選址問題等。當(dāng)然，要求出一個圖的任意兩點(diǎn)間的最短距路，只需將圖中每一個頂點(diǎn)依次視為始點(diǎn)，然后用Dij

15、kstra算法就可以了。vDijkstra算法在物流配送中的應(yīng)用 vOSPFopen shortest path first, 開放最短路徑優(yōu)先算法是Dijkstra算法在網(wǎng)絡(luò)路由中的一個具體實(shí)現(xiàn)。 18返回 結(jié)束7.4 .1 Dijkstra算法vDijkstra算法要求圖上的權(quán)是非負(fù)數(shù)，否則結(jié)果不正確；vDijkstra算法同樣適用于無向圖，此時一個無向邊次相當(dāng)于兩個有向邊。v利用求最短路的方法求最長路。由于存在負(fù)權(quán)求最長路和負(fù)權(quán)等價(jià)），所以在這里Dijkstra算法不適用了，必須采用Floyd算法-動態(tài)規(guī)劃算法vFloyd算法的功能是通過一個圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣.1

16、9返回 結(jié)束7.4.2 Floyd算法v如果有一個矩陣D=d(ij)，其中d(ij)0表示i城市到j(luò)城市的距離。若i與j之間無路可通，那么d(ij)就是無窮大。又有d(ii)=0。通過這個距離矩陣D，把任意兩個城市之間的最短路徑找出來。v【分析】 對于任何一個城市而言，i 到 j 的最短距離不外乎存在經(jīng)過 i 與 j 之間的k和不經(jīng)過k兩種可能，所以可以令k=1，2，3，.，n(n是城市的數(shù)目)，檢查d(ij)與d(ik)+d(kj)的值；d(ik)與d(kj)分別是目前為止所知道的 i 到 k 與 k 到 j 的最短距離，因此d(ik)+d(kj)就是 i 到 j 經(jīng)過k的最短距離。所以，若

17、有d(ij)d(ik)+d(kj)，就表示從 i 出發(fā)經(jīng)過 k 再到j(luò)的距離要比原來的 i 到 j 距離短，自然把i到j(luò)的d(ij)重寫為d(ik)+d(kj)，每當(dāng)一個k查完了，d(ij)就是目前的 i 到 j 的最短距離。重復(fù)這一過程，最后當(dāng)查完所有的k時，d(ij)里面存放的就是 i 到 j 之間的最短距離了。20返回 結(jié)束7.4.2 Floyd算法定義定義7.4.1:已知矩陣已知矩陣A(aij)ml，B(bjk)ln，規(guī)定，規(guī)定CA*B(cij)mn，其中，其中cijmin(ai1b1j, ai2b2j, , ailblj)定義定義7.4.2已知矩陣已知矩陣A(aij)mn，B(bij

18、)mn，規(guī)定，規(guī)定DA B(dij)mn，其中，其中dijmin(aij,bij)可以利用上面定義的運(yùn)算求任意兩點(diǎn)間的最短距離?？梢岳蒙厦娑x的運(yùn)算求任意兩點(diǎn)間的最短距離。已知已知n階加權(quán)簡單圖階加權(quán)簡單圖G，設(shè)，設(shè)D(dij)mn 是圖是圖G的邊權(quán)矩陣，的邊權(quán)矩陣，即即dij(i,j)(若若G是有向圖，則是有向圖，則dij),若結(jié)點(diǎn)若結(jié)點(diǎn)i到到結(jié)點(diǎn)結(jié)點(diǎn) j無邊相連時，則取無邊相連時，則取dij。然后依次計(jì)算出矩陣。然后依次計(jì)算出矩陣D2, D3, Dn及及S21返回 結(jié)束7.4.2 Floyd算法其中 D2D*D( )nn d(2)ij=mindi1+d1j，di2+d2j，dindnjd

19、(2)ij表示從vi出發(fā)兩步可以到達(dá)vi的道路中距離最短者。D3D2*D( )nn d(k)ij表示從vi出發(fā)k步可以到達(dá)vj的道路中距離最短者DnDn-1*D( )nnSD D2 D3 Dn(Sij)nn由定義可知dijk表示從結(jié)點(diǎn)i到j(luò)經(jīng)k邊的路在有向圖中即為有向路中的長度最短者，而Sij為結(jié)點(diǎn)i到j(luò)的所有路若是有向圖即為有向路中的長度最短者。 Floyd算法的時間復(fù)雜性是O(n4)。dij2dij3dnij22返回 結(jié)束7.4.2 Floyd算法v求下圖各點(diǎn)間的最短路徑213465121733621D1 2 3 4 5 612345623返回 結(jié)束7.4.2 Floyd算法v解：D(2)

20、*d14min+,1+3,2+1, +, +, +,24返回 結(jié)束7.4.2 Floyd算法v類似可得：D(3)D(5)D(4)25返回 結(jié)束7.4.2 Floyd算法v所以：SD D(2) D(3) D(4) D(5)(sij)66S21346512173362126返回 結(jié)束7.4.3 Floyd-Warshall算法Floyd-Warshall算法是解決任意兩點(diǎn)間的最短路徑的一種算法。 基本思想： 通過求解矩陣序列D(0)，D(1)，D(n)來實(shí)現(xiàn)問題的求解。27返回 結(jié)束7.4.3 Floyd-Warshall算法其中：D(0)圖的距離矩陣；D(n)最終解；dij邊(vi,vj)的權(quán)值

21、d(k)ij從vi到vj在所經(jīng)過的頂點(diǎn)號k最短路徑長度。即通過依次比較頂點(diǎn)修改路徑實(shí)現(xiàn)求解的。 對于任意兩個頂點(diǎn)vi，vj，對于新比較的頂點(diǎn)vk一旦出現(xiàn)d(k-1)ijdikdkj，則修改對應(yīng)的d(k)ij。28返回 結(jié)束7.4.3 Floyd-Warshall算法v例：求下圖各點(diǎn)間的最短路徑213465121733621D1 2 3 4 5 612345629返回 結(jié)束7.4.3 Floyd-Warshall算法v解：比較經(jīng)過頂點(diǎn)號1的矩陣213465121733621D(0)1 2 3 4 5 6123456D(1)1 2 3 4 5 6123456無改變30返回 結(jié)束7.4.3 Floyd-Warshall算法v解：比較經(jīng)過頂點(diǎn)號2的矩陣213465121733621D(1)1 2 3 4 5 6123456D(2)1 2 3 4 5 612345648d(1)14d12d24所以修改d(2)14d(1)16d12d26所以修改d(2)1631返回 結(jié)束7.4.3 Floyd-Warshall算法v解：比較經(jīng)過頂點(diǎn)號3的矩陣213465121733621D(2)1 2 3 4 5 6