離散數(shù)學第7章圖論最短路問題

離散數(shù)學第7章圖論最短路問題7.4最短路問題非帶權圖的路徑長度是指此路徑上邊的條數(shù)。帶權圖的路徑長度是指路徑上各邊的權之和[距離矩陣]對上述網絡，定義D=(dij)nn，n=|V|

wij

當<vi,vj>E

dij=其它[帶權路徑長度]對上述網絡，路徑v1,v2,…,vk的帶權路徑長度定義為7.4最短路問題最短路問題在實際工作中應用1、通訊網絡中最可靠問題2、最大容量問題3、統(tǒng)籌方法中求關鍵路線4、背包問題5、選址問題6、工件加工順序問題7、中國郵遞員問題背包問題(Knapsackproblem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。

7.4最短路問題例一位旅客要從A城到B城他希望選擇一條途中中轉次數(shù)最少的路線；他希望選擇一條途中所花時間最短的路線；他希望選擇一條途中費用最小的路線；v5v4v3v2v1v0

1006030101020

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

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

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

7.4.1Dijkstra算法Dijkstra算法基本思想:把圖中所有結點分為兩組，每一個結點對應一個距離值。第一組：包括已確定最短路徑的結點，結點對應的距離值是由v0到此結點的最短路徑長度；第二組：包括尚未確定最短路徑的結點，結點對應的距離值是v0經由第一組結點（中間結點）至此結點的最短路徑長度。按最短路徑長度遞增的順序把第二組的結點加到第一組中去，直至v0可達的所有結點都包含于第一組。在這個過程中，總保持從v0到第一組各結點的最短路徑長度都不大于從v0至第二組任何結點的路徑長度。7.4.1Dijkstra算法設源點為v0初始時v0進入第一組，v0的距離值為0；第二組包含其它所有結點，這些結點對應的距離值這樣確定（設vi為第二組中的結點）

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

dij7.4.1Dijkstra算法下面給出該算法的框圖：通過框圖，容易計算該算法計算量。7.4.1Dijkstra算法下面通過一個實例來說明Dijkstra算法是如何工作的?！?.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結束u＝z，S＝{a,c,b,d,e,z}從a到z的最短路的長度為13。7.4.1Dijkstra算法Dijkstra算法(另外一種說明)求有向網絡G=(V,A)中結點v1

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

標記結點v1到vi

的距離。

S為已取得最短路的結點集合，其中每個結點在U中有固定標號標記取得的最短路的長度；S為未取得最短路的結點集合，其中每個結點在U中有臨時標號。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.選固定標號：在S(m)中求vk，使得uk(m)=min{uj(m)|vjS(m)}。若uk(m)=，則S(m)中的結點無最短路徑；否則轉2。2.判結束：令S(m+1)

S(m)

{vk},S(m+1)

S(m)

{vk}

若m=n1，結束。3.修改臨時標號：對所有vjS(m+1)

，令

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

,uk(m)+dkj}，m

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

對于任何一個城市而言，i到j的最短距離不外乎存在經過i與j之間的k和不經過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經過k的最短距離。所以，若有d(ij)>d(ik)+d(kj)，就表示從i出發(fā)經過k再到j的距離要比原來的i到j距離短，自然把i到j的d(ij)重寫為d(ik)+d(kj)<這里就是動態(tài)規(guī)劃中的決策>，每當一個k查完了，d(ij)就是目前的i到j的最短距離。重復這一過程，最后當查完所有的k時，d(ij)里面存放的就是i到j之間的最短距離了<這就是動態(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)可以利用上面定義的運算求任意兩點間的最短距離。已知n階加權簡單圖G，設D＝(dij)m×n

是圖G的邊權矩陣，即dij＝ω(i,j)(若G是有向圖，則dij＝ω<i,j>),若結點i到結點j無邊相連時，則取dij＝∞。然后依次計算出矩陣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ā)兩步可以到達vi的道路中距離最短者。D[3]＝D[2]*D＝()n×n……d(k)ij表示從vi出發(fā)k步可以到達vj的道路中距離最短者D[n]＝D[n-1]*D＝()n×nS＝DD[2]D[3]…D[n]＝(Sij)n×n由定義可知dij[k]表示從結點i到j經k邊的路（在有向圖中即為有向路）中的長度最短者，而Sij為結點i到j的所有路（若是有向圖即為有向路）中的長度最短者。

Floyd算法的時間復雜性是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算法類似可得：∞∞∞346∞∞∞∞∞5∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞D(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算法是解決任意兩點間的最短路徑的一種算法。

基本思想：通過求解矩陣序列D(0)，D(1)，…，D(n)來實現(xiàn)問題的求解。7.4.3Floyd-Warshall算法其中：D(0)——圖的距離矩陣；D(n)——最終解；dij——邊(vi,vj)的權值d(k)ij——從vi到vj在所經過的頂點號≤k最短路徑長度。即通過依次比較頂點修改路徑實現(xiàn)求解的。對于任意兩個頂點vi，vj，對于新比較的頂點vk一旦出現(xiàn)d(k-1)ij＞dik＋dkj，則修改對應的d(k)ij。7.4.3Floyd-Warshall算法例：求下圖各點間的最短路徑213465121733621D＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞1234561234567.4.3Floyd-Warshall算法解：比較經過頂點號≤1的矩陣213465121733621D(0)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(1)＝∞12∞∞∞∞∞13∞7∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456無改變7.4.3Floyd-Warshall算法解：比較經過頂點號≤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算法解：比較經過頂點號≤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算法解：比較經過頂點號≤4的矩陣213465121733621D(3)＝∞12348∞∞1237∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞∞∞∞∞123456123456D(4)＝∞12248∞∞1237∞∞∞12∞∞∞∞∞∞3∞∞∞∞∞6∞∞