離散數(shù)學(xué)第7章圖論最短路問(wèn)題

離散數(shù)學(xué)第7章圖論最短路問(wèn)題7.4最短路問(wèn)題非帶權(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)題最短路問(wèn)題在實(shí)際工作中應(yīng)用1、通訊網(wǎng)絡(luò)中最可靠問(wèn)題2、最大容量問(wèn)題3、統(tǒng)籌方法中求關(guān)鍵路線4、背包問(wèn)題5、選址問(wèn)題6、工件加工順序問(wèn)題7、中國(guó)郵遞員問(wèn)題背包問(wèn)題(Knapsackproblem)是一種組合優(yōu)化的NP完全問(wèn)題。問(wèn)題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。問(wèn)題的名稱來(lái)源于如何選擇最合適的物品放置于給定背包中。

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)車行經(jīng)的距離。Dijkstra算法可以用來(lái)找到兩個(gè)城市之間的最短路徑。

7.4.1Dijkstra算法Dijkstra算法基本思想:把圖中所有結(jié)點(diǎn)分為兩組，每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)距離值。第一組：包括已確定最短路徑的結(jié)點(diǎn)，結(jié)點(diǎn)對(duì)應(yīng)的距離值是由v0到此結(jié)點(diǎn)的最短路徑長(zhǎng)度；第二組：包括尚未確定最短路徑的結(jié)點(diǎn)，結(jié)點(diǎn)對(duì)應(yīng)的距離值是v0經(jīng)由第一組結(jié)點(diǎn)（中間結(jié)點(diǎn)）至此結(jié)點(diǎn)的最短路徑長(zhǎng)度。按最短路徑長(zhǎng)度遞增的順序把第二組的結(jié)點(diǎn)加到第一組中去，直至v0可達(dá)的所有結(jié)點(diǎn)都包含于第一組。在這個(gè)過(guò)程中，總保持從v0到第一組各結(jié)點(diǎn)的最短路徑長(zhǎng)度都不大于從v0至第二組任何結(jié)點(diǎn)的路徑長(zhǎng)度。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算法下面通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明Dijkstra算法是如何工作的。∞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算法0.初始化：u1(1)

0，uj(1)d1j(j=2,3,…,n)S(1)

{v1}，S(1)

{v2

,v3

,…

,vn}，m=1;1.選固定標(biāo)號(hào)：在S(m)中求vk，使得uk(m)=min{uj(m)|vjS(m)}。若uk(m)=，則S(m)中的結(jié)點(diǎn)無(wú)最短路徑；否則轉(zhuǎn)2。2.判結(jié)束：令S(m+1)

S(m)

{vk},S(m+1)

S(m)

{vk}

若m=n1，結(jié)束。3.修改臨時(shí)標(biāo)號(hào)：對(duì)所有vjS(m+1)

，令

uj(m+1)=min{uj(m)

,uk(m)+dkj}，m

m+1；轉(zhuǎn)1。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算法定義7.4.1:已知矩陣A＝(aij)m×l，B＝(bjk)l×n，規(guī)定C＝A*B＝(cij)m×n，其中cij＝min(ai1＋b1j,ai2＋b2j,…,ail＋blj)定義已知矩陣A＝(aij)m×n，B＝(bij)m×n，規(guī)定D＝AB＝(dij)m×n，其中dij＝min(aij,bij)可以利用上面定義的運(yùn)算求任意兩點(diǎn)間的最短距離。已知n階加權(quán)簡(jiǎn)單圖G，設(shè)D＝(dij)m×n

是圖G的邊權(quán)矩陣，即dij＝ω(i,j)(若G是有向圖，則dij＝ω<i,j>),若結(jié)點(diǎn)i到結(jié)點(diǎn)j無(wú)邊相連時(shí)，則取dij＝∞。然后依次計(jì)算出矩陣D[2],D[3],…,D[n]及S7.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算法類似可得：∞∞∞346∞∞∞∞∞5∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞D(zhuǎn)(3)＝D(5)＝D(4)＝∞∞∞∞∞6∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞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算法其中：D(0)——圖的距離矩陣；D(n)——最終解；dij——邊(vi,vj)的權(quán)值d(k)ij——從vi到vj在所經(jīng)過(guò)的頂點(diǎn)號(hào)≤k最短路徑長(zhǎng)度。即通過(guò)依次比較頂點(diǎn)修改路徑實(shí)現(xiàn)求解的。對(duì)于任意兩個(gè)頂點(diǎn)vi，vj，對(duì)于新比較的頂點(diǎn)vk一旦出現(xiàn)d(k-1)ij＞dik＋dkj，則修改對(duì)應(yīng)的d(k)ij。7.4.3Floyd-Warshall算法例：求下圖各點(diǎn)間的最短路徑213465121733621D＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞1234561234567.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∞∞