圖論4最短路問題課件

第七章圖論引言7.1圖的基本概念7.27.3圖的矩陣表示7.4最短路徑問題7.5圖的匹配8.1Euler圖和Hamilton圖8.2樹8.38.47.4最短路問題一、問題的提出

賦權(quán)圖（網(wǎng)絡(luò)）：G=(V,E)中，給每條邊a=<vi,vj>賦予一個非負(fù)實數(shù)權(quán)wij

，得到一個有向網(wǎng)絡(luò)7.4最短路問題路徑路徑長度

非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)。帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和[距離矩陣]

對上述網(wǎng)絡(luò)，定義D=(dij)nn，n=|V|

wij

當(dāng)<vi,vj>E

dij=其它[帶權(quán)路徑長度]

對上述網(wǎng)絡(luò)，路徑v1,v2,…,vk的帶權(quán)路徑長度定義為7.4最短路問題例一位旅客要從A城到B城他希望選擇一條途中中轉(zhuǎn)次數(shù)最少的路線；他希望選擇一條途中所花時間最短的路線；他希望選擇一條途中費用最小的路線；v5v4v3v2v1v0

1006030101020

550這些問題均是帶權(quán)圖上的最短路徑問題。邊上的權(quán)表示一站邊上的權(quán)代表距離邊的權(quán)代表費用7.4最短路問題Dijkstra算法Floyd算法Floyd-Warshall算法7.4最短路問題Dijkstra算法

Dijkstra算法是由荷蘭計算機科學(xué)家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。

荷蘭計算機科學(xué)教授EdsgerW.Dijkstra(1930-)在1972年獲得美國計算機協(xié)會授予的圖靈獎，這是計算機科學(xué)中最具聲望的獎項之一。Dijkstra算法是求出一個連通加權(quán)簡單圖中從結(jié)點a到結(jié)點z的最短路。邊(i,j)的權(quán)ω(i,j)＞0，且結(jié)點x的標(biāo)號為L(x)。結(jié)束時，L(z)是從a到z的最短長度。舉例來說，如果圖中的頂點表示城市，而邊上的權(quán)重表示城市間開車行經(jīng)的距離。Dijkstra算法可以用來找到兩個城市之間的最短路徑。

7.4.1Dijkstra算法設(shè)源點為v0初始時v0進入第一組，v0的距離值為0；第二組包含其它所有結(jié)點，這些結(jié)點對應(yīng)的距離值這樣確定（設(shè)vi為第二組中的結(jié)點）

然后每次從第二組的結(jié)點中選一個其距離值為最小的結(jié)點vm加到第一組中。每往第一組加入一個結(jié)點vm，就要對第二組的各結(jié)點的距離值作一次修正（設(shè)vi為第二組的結(jié)點）：若加進vm做中間結(jié)點使得v0至vi的路徑長度更短（即vi的距離值>vm的距離值+Wmi），則要修改vi的距離（vi的距離值←vm的距離值+Wmi）。修改后再選距離值最小的一個結(jié)點加入到第一組中，…。如此進行下去，直至第一組囊括圖的所有結(jié)點或再無可加入第一組的結(jié)點存在。顯然，這種從第二組的結(jié)點中選距離值最小的結(jié)點擴展是一種貪心策略。7.4.1Dijkstra算法procedureDijkstra(G:所有權(quán)都為正數(shù)的加權(quán)連通簡單圖){G帶有頂點a＝v0,v1,…,vn＝z和權(quán)ω(vi,vj)，若(vi,vj)不是G的邊，則ω(vi,vj)＝∞}fori:＝1tonL(vi)＝∞L(a):＝0S:＝（初始化標(biāo)記，a的標(biāo)記為0，其余結(jié)點標(biāo)記為∞，S是空集}while

zS

beginu:＝不屬于S的L(u)最小的一個頂點S:＝S∪{u}for

所有不屬于S的頂點vifL(u)＋ω(u,v)＜L(v)thenL(v):＝L(u)＋ω(u,v){這樣就給S中添加帶最小標(biāo)記的頂點并且更新不在S中的頂點的標(biāo)記}end{L(z)＝從a到z的最短長度}

dij7.4.1Dijkstra算法下面給出該算法的框圖：通過框圖，容易計算該算法計算量。7.4.1Dijkstra算法7.4.1Dijkstra算法

0次迭代

L(a)＝0L(b)＝L(c)＝L(d)＝L(e)＝L(z)＝∞S＝1次迭代u＝a，S＝{a}L(a)＋ω(a,b)＝0＋4＝4＜L(b)L(a)＋ω(a,c)＝0＋2＝2＜L(c)L(a)＋ω(a,d)＝0＋∞＝∞L(a)＋ω(a,e)＝0＋∞＝∞L(a)＋ω(a,z)＝0＋∞＝∞L(b)＝4，L(c)＝2，L(d)＝L(e)＝L(z)＝∞2次迭代u＝c，S＝{a,c}L(c)＋ω(c,b)＝2＋1＝3＜L(b)L(c)＋ω(c,d)＝2＋8＝10＜L(d)L(c)＋ω(c,e)＝2＋10＝12＜L(e)L(c)＋ω(c,z)＝2＋∞＝∞L(b)＝3，L(d)＝10，L(e)＝12，L(z)＝∞3次迭代u＝b，S＝{a,c,b}L(b)＋ω(b,d)＝3＋5＝8＜L(d)L(b)＋ω(b,e)＝3＋∞＝∞145623108abcdez用Dijkstra算法求a和z之間最短路所用的步驟。L(b)＋ω(b,z)＝3＋∞＝∞L(d)＝8，L(e)＝12，L(z)＝∞4次迭代u＝d，S＝{a,c,b,d}L(d)＋ω(d,e)＝8＋2＝10＜L(e)L(d)＋ω(d,z)＝8＋6＝14＜L(z)L(e)＝10，L(z)＝145次迭代u＝e，S＝{a,c,b,d,e}L(e)＋ω(e,z)＝10＋3＝13＜L(z)L(z)＝13結(jié)束u＝z，S＝{a,c,b,d,e,z}從a到z的最短路的長度為13。7.4.1Dijkstra算法Dijkstra算法(另外一種說明)求有向網(wǎng)絡(luò)G=(V,A)中結(jié)點v1

到其它結(jié)點的最短距離。設(shè)D為G的距離矩陣，n=|V|，向量U=(u1,u2,…,un)的ui

標(biāo)記結(jié)點v1到vi

的距離。

S為已取得最短路的結(jié)點集合，其中每個結(jié)點在U中有固定標(biāo)號標(biāo)記取得的最短路的長度；S為未取得最短路的結(jié)點集合，其中每個結(jié)點在U中有臨時標(biāo)號。7.4.1Dijkstra算法Dijkstra算法只求出圖中一個特定的頂點到其他各定點的最短路。但在許多實際問題中，需求出任意兩點之間的最短路，如全國各城市之間最短的航線，選址問題等。當(dāng)然，要求出一個圖的任意兩點間的最短距路，只需將圖中每一個頂點依次視為始點，然后用Dijkstra算法就可以了。Dijkstra算法在物流配送中的應(yīng)用OSPF（openshortestpathfirst,開放最短路徑優(yōu)先）算法是Dijkstra算法在網(wǎng)絡(luò)路由中的一個具體實現(xiàn)。7.4.1Dijkstra算法Dijkstra算法要求圖上的權(quán)是非負(fù)數(shù)，否則結(jié)果不正確；Dijkstra算法同樣適用于無向圖，此時一個無向邊次相當(dāng)于兩個有向邊。利用求最短路的方法求最長路。由于存在負(fù)權(quán)（求最長路和負(fù)權(quán)等價），所以在這里Dijkstra算法不適用了，必須采用Floyd算法--動態(tài)規(guī)劃算法Floyd算法的功能是通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣.7.4.2Floyd算法如果有一個矩陣D=[d(ij)]，其中d(ij)>0表示i城市到j(luò)城市的距離。若i與j之間無路可通，那么d(ij)就是無窮大。又有d(ii)=0。通過這個距離矩陣D，把任意兩個城市之間的最短路徑找出來?！痉治觥?/p>

對于任何一個城市而言，i到j(luò)的最短距離不外乎存在經(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(luò)的最短距離，因此d(ik)+d(kj)就是i到j(luò)經(jīng)過k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發(fā)經(jīng)過k再到j(luò)的距離要比原來的i到j(luò)距離短，自然把i到j(luò)的d(ij)重寫為d(ik)+d(kj)<這里就是動態(tài)規(guī)劃中的決策>，每當(dāng)一個k查完了，d(ij)就是目前的i到j(luò)的最短距離。重復(fù)這一過程，最后當(dāng)查完所有的k時，d(ij)里面存放的就是i到j(luò)之間的最短距離了<這就是動態(tài)規(guī)劃中的記憶化搜索>。7.4.2Floyd算法其中D[2]＝D*D＝()n×nd(2)ij=min{di1+d1j，di2+d2j，…，din＋dnj}d(2)ij表示從vi出發(fā)兩步可以到達(dá)vi的道路中距離最短者。D[3]＝D[2]*D＝()n×n……d(k)ij表示從vi出發(fā)k步可以到達(dá)vj的道路中距離最短者D[n]＝D[n-1]*D＝()n×nS＝DD[2]D[3]…D[n]＝(Sij)n×n由定義可知dij[k]表示從結(jié)點i到j(luò)經(jīng)k邊的路（在有向圖中即為有向路）中的長度最短者，而Sij為結(jié)點i到j(luò)的所有路（若是有向圖即為有向路）中的長度最短者。Floyd算法的時間復(fù)雜性是O(n4)。7.4.2Floyd算法求下圖各點間的最短路徑213465121733621D＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞1234561234567.4.2Floyd算法解：D(2)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞*＝∞∞2348∞∞∞236∞∞∞∞∞4∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞d14＝min{∞+∞,1+3,2+1,∞+∞,∞+∞,∞+∞,}7.4.2Floyd算法所以：S＝DD(2)D(3)D(4)D(5)＝(sij)6×6S＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞213465121733621????7.4.3Floyd-Warshall算法Floyd-Warshall算法是解決任意兩點間的最短路徑的一種算法。

基本思想：通過求解矩陣序列D(0)，D(1)，…，D(n)來實現(xiàn)問題的求解。7.4.3Floyd-Warshall算法解：比較經(jīng)過頂點號≤1的矩陣213465121733621D(0)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(1)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456無改變7.4.3Floyd-Warshall算法解：比較經(jīng)過頂點號≤2的矩陣213465121733621D(1)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(2)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞12345612345648d(1)14＞d12＋d24所以修改d(2)14d(1)16＞d12＋d26所以修改d(2)167.4.3Floyd-Warshall算法解：比較經(jīng)過頂點號≤3的矩陣213465121733621D(2)＝∞124∞8∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(3)＝∞124∞8∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞1234561234564233d(2)14＞d13＋d34d(2)15＞d13＋d35d(2)24＞d23＋d34d(2)25＞d23＋d357.4.3Floyd-Warshall算法解：比較經(jīng)過頂點號≤4的矩陣213465121733621D(3)＝∞12348∞∞1237∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(4)＝∞12248∞∞1237∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456654d(3)16＞d13＋d34＋d46d(3)26＞d23＋d34＋d46d(3)36＞d34＋d467.4.3Floyd-Warshall算法解：比較經(jīng)過頂點號≤5的矩陣213465121733621D(4)＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(5)＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456無改變7.4.3Floyd-Warshall算法解：比較經(jīng)過頂點號≤6的矩陣213465121733621D(5)＝∞12346∞∞1235∞∞∞124∞∞∞∞