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

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

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

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

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

wij

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

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

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

1006030101020

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

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

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

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

然后每次從第二組的結(jié)點(diǎn)中選一個(gè)其距離值為最小的結(jié)點(diǎn)vm加到第一組中。每往第一組加入一個(gè)結(jié)點(diǎn)vm，就要對(duì)第二組的各結(jié)點(diǎn)的距離值作一次修正（設(shè)vi為第二組的結(jié)點(diǎn)）：若加進(jìn)vm做中間結(jié)點(diǎn)使得v0至vi的路徑長(zhǎng)度更短（即vi的距離值>vm的距離值+Wmi），則要修改vi的距離（vi的距離值←vm的距離值+Wmi）。修改后再選距離值最小的一個(gè)結(jié)點(diǎn)加入到第一組中，…。如此進(jìn)行下去，直至第一組囊括圖的所有結(jié)點(diǎn)或再無(wú)可加入第一組的結(jié)點(diǎn)存在。顯然，這種從第二組的結(jié)點(diǎn)中選距離值最小的結(jié)點(diǎn)擴(kuò)展是一種貪心策略。7.4.1Dijkstra算法procedureDijkstra(G:所有權(quán)都為正數(shù)的加權(quán)連通簡(jiǎn)單圖){G帶有頂點(diǎn)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é)點(diǎn)標(biāo)記為∞，S是空集}while

zS

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

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

dij7.4.1Dijkstra算法下面給出該算法的框圖：通過(guò)框圖，容易計(jì)算該算法計(jì)算量。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的最短路的長(zhǎng)度為13。7.4.1Dijkstra算法Dijkstra算法(另外一種說(shuō)明)求有向網(wǎng)絡(luò)G=(V,A)中結(jié)點(diǎn)v1

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

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

的距離。

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

對(duì)于任何一個(gè)城市而言，i到j(luò)的最短距離不外乎存在經(jīng)過(guò)i與j之間的k和不經(jīng)過(guò)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)過(guò)k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發(fā)經(jīng)過(guò)k再到j(luò)的距離要比原來(lái)的i到j(luò)距離短，自然把i到j(luò)的d(ij)重寫(xiě)為d(ik)+d(kj)<這里就是動(dòng)態(tài)規(guī)劃中的決策>，每當(dāng)一個(gè)k查完了，d(ij)就是目前的i到j(luò)的最短距離。重復(fù)這一過(guò)程，最后當(dāng)查完所有的k時(shí)，d(ij)里面存放的就是i到j(luò)之間的最短距離了<這就是動(dòng)態(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é)點(diǎn)i到j(luò)經(jīng)k邊的路（在有向圖中即為有向路）中的長(zhǎng)度最短者，而Sij為結(jié)點(diǎn)i到j(luò)的所有路（若是有向圖即為有向路）中的長(zhǎng)度最短者。Floyd算法的時(shí)間復(fù)雜性是O(n4)。7.4.2Floyd算法求下圖各點(diǎn)間的最短路徑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算法是解決任意兩點(diǎn)間的最短路徑的一種算法。

基本思想：通過(guò)求解矩陣序列D(0)，D(1)，…，D(n)來(lái)實(shí)現(xiàn)問(wèn)題的求解。7.4.3Floyd-Warshall算法解：比較經(jīng)過(guò)頂點(diǎn)號(hào)≤1的矩陣213465121733621D(0)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(1)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456無(wú)改變7.4.3Floyd-Warshall算法解：比較經(jīng)過(guò)頂點(diǎn)號(hào)≤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)過(guò)頂點(diǎn)號(hào)≤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)過(guò)頂點(diǎn)號(hào)≤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)過(guò)頂點(diǎn)號(hào)≤5的矩陣213465121733621D(4)＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(5)＝∞12346∞∞1235∞∞∞124∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456無(wú)改變7.4.3Floyd-Warshall算法解：比較經(jīng)過(guò)頂點(diǎn)號(hào)≤6的矩陣213465121733621D(5)＝∞12346∞∞1235∞∞∞124∞∞∞∞