-圖論模型：最短路-PPT課件

1、第六章 圖論方法 7.1 圖論的基本概念定義1 一個有序二元組（V,E）稱為一個圖，記為G=（V,E），其中 V稱為G的頂點集，V，V中的元素稱為頂點或結(jié)點，簡稱點； E稱為G的邊集，其元素稱為邊，它連接V中的兩個點，如果這兩個點是無序的，則稱該邊為無向邊；否則，稱為有向邊。如果Vv1,v2,vn是有限非空點集，則稱G為有限圖或n階圖。如果G的每條邊都是無向邊，則稱G為無向圖；如果G的每條邊都是有向邊，則稱G為有向圖。否則稱G為混合圖。并且常記Ee1,e2,em,(ek=vivj,i,j=1,2,n),對于一個圖G=（V,E），人們通常用一個圖形來表示，稱其為圖解。凡是有向圖，在圖解上用箭頭標(biāo)

2、明其方向。 則G（V,E）是一個有4個頂點、6條邊的圖，其圖解如下圖： 一個圖會有許多外形不同的圖解，如上圖。稱點vi,vj為邊vivj的端點。在有向圖中，稱點vi,vj分別為有向邊vivj的始點和終點；稱邊vivj為點vi的出邊，為點vj入邊。 由邊連接的兩個點稱為相鄰的點；有一個公共端點的邊稱為相鄰邊；邊和它的端點稱為互相關(guān)聯(lián)。常用d(v)表示圖G中與頂點v關(guān)聯(lián)的邊的數(shù)目，d(v)稱為頂點v的度數(shù)；用N（v）表示圖G中所有與頂點v相鄰的頂點的集合。定義2 若將圖G的每條邊e都對應(yīng)一個實數(shù)F(e)，則稱F（e） 為該邊的權(quán)，并稱圖G為賦權(quán)圖，記為G=(V,E,F)。定義3 設(shè)G=(V,E)是

3、一個圖， ，則稱是G的一個通路。如果通路中沒有相同的邊，則稱此通路為道路；始點和終點相同的道路稱為圈或回路；如果通路中既沒有相同的邊，又沒有相同的頂點，則稱此通路為路徑，簡稱路。定義4 任意兩點都有通路的圖稱為連通圖。定義5 連通而無圈的圖稱為樹，常用T表示樹。 7.2 最短路模型及其算法最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最為廣泛的問題之一，不少優(yōu)化問題可化為這個模型。如管道的鋪設(shè)、運輸網(wǎng)絡(luò)的設(shè)計、線路安排、設(shè)備更新、廠區(qū)布局等。定義1 設(shè)P（u,v）是賦權(quán)圖G=(V,E,F)中從點u到點v的路徑，用E(P)表示路徑P(u,v)的全部邊的集合，記為， ，則稱F(P)為路徑P(u,v) 的權(quán)或長度。定義

4、2 若P0(u,v)是G中連接u,v的路徑，且對任意在G中連接u,v的路徑P(u,v)，都有F(P0)F(P),則稱P0(u,v)是G中連接u,v的最短路徑。 根據(jù)上述定理，著名計算機專家狄克斯特拉（Dijkstra）給出了求G中某一點到其他各點最短路徑的算法標(biāo)號法：T標(biāo)號與P標(biāo)號。T標(biāo)號為試探性標(biāo)號，P標(biāo)號為永久性標(biāo)號。給vi點一個P標(biāo)號時，表示從v0（起點）到點vi的最短路權(quán)，vi點的標(biāo)號不再改變；給vi點一個T標(biāo)號時，表示從v0到vi的估計最短路權(quán)，是一種臨時標(biāo)號。凡沒有得到P標(biāo)號的點都標(biāo)有T標(biāo)號。 算法每一步是把某一點的T標(biāo)號改為P標(biāo)號，當(dāng)終點得到P標(biāo)號時全部計算結(jié)束。其具體步驟如下：

5、（1）賦初值：給起點v0以P標(biāo)號，P(v0)0，其余各點vi均為T標(biāo)號,T（vi）+；（2）更新所有的T標(biāo)號：若vi點為剛得到的P標(biāo)號的點,考慮這樣的點vj，邊vivjE，且vj為T標(biāo)號，對vj的T標(biāo)號進行如下的更改：（3）比較所有T標(biāo)號的點，把最小者改為P標(biāo)號，當(dāng)存在兩個以上最小時，可同時改為P標(biāo)號，若全部點均為P標(biāo)號，則停止； 例2 求下圖中V0到其余各點的最短路。 迭代次數(shù)T(v0)T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)T(v7)P標(biāo)號10+20281+v03281+v3428+10+v1583+10+V46861011V5771011V28911V6911V7最短

6、路權(quán)027136911父點v0v0v5v0v1v4V2v4 例2(設(shè)備更新問題)某企業(yè)使用一種設(shè)備,每年年初,企業(yè)都要作出決定,如果要繼續(xù)使用舊的, ;若購買一臺新設(shè)備,要付購買費.使制定一個5年更新計劃,使總費用最少?已知設(shè)備每年年初的購買費分別為:11,11,12,12,13,使用不同時間設(shè)備所需的維修費為:解：設(shè)bi表示設(shè)備在第i年年初的購買費，ci表示設(shè)備使用 i年后的維修費，把這個問題化為求有向賦權(quán)圖G=（V,E,F）中的最短路問題。設(shè)備年齡0112233445維修費5681118 賦權(quán)圖如上圖所示，這樣設(shè)備更新問題就變?yōu)椋簭膙1到v6的最短路問題。由狄克斯特拉（Dijkstra）算

7、法列表如下：迭代次數(shù)T(v1)T(v2)T(v3)T(v4)T(v5)T(v6)P標(biāo)號10+V121622304159V2322304157V34304153V454153V5653V6最短路權(quán)01622304153父點V1V1V1V1V1V3或v4 計算結(jié)果表明：路徑v1v3v6或v1v4v6為兩條最短路徑，路長均為53。即第1年、第3年個購買一臺新設(shè)備，或第1年、第4年各購買一臺新設(shè)備為最優(yōu)決策。最小費用為53.例3 如下圖表示某區(qū)域的交通網(wǎng)絡(luò)，各條旁邊所注的數(shù)字表示通過該公路所估計行駛的時間（單位：小時）。試問S到T估計至少要行駛多少小時？并寫出最短路徑。解：狄克斯特拉（Dijkstra

8、）算法列表如下： 迭代次數(shù)T（S）T(V1)T(V2)T(V3)T（V4）T（V5）T（V6）T（T）P標(biāo)號10+S24+1+45+V3332635+V2 436359V1 56357V56657V6 767V4 87D最短路權(quán)03216357父點S V3V3SV3V3SV1 最短路模型還可以應(yīng)用于中心選址問題。所謂中心選址問題就是在一個網(wǎng)絡(luò)中選擇一點，建立公用服務(wù)設(shè)施，為該網(wǎng)絡(luò)中的客戶提供服務(wù)，使得服務(wù)效率最高。比如一個區(qū)域的消防站、自來水廠、學(xué)校、變電站、銀行商店等選址。為了提高服務(wù)效率，自然的想法是將 這些設(shè)施建立在中心地點。對于規(guī)則的網(wǎng)絡(luò)，例如圓形、矩形等，中心地點是顯而易見的，然而對

9、于更多的網(wǎng)絡(luò)是不規(guī)則的。應(yīng)此，我們引入兩個定義。 例4 教育部們打算在某新建城區(qū)建一所學(xué)校,讓附近七個居民區(qū)的學(xué)生就近入學(xué)。七個居民區(qū)之間的道路如下圖所示.學(xué)校應(yīng)建在哪個居民區(qū)，才能使大家都方便？（圖中距離單位：百米）解：由狄克斯特拉（Dijkstra）算法計算得各居民之間的最短距離列表如下: ABCDEFG d (vi)di,jA034578101037B3032457724C4305568831D52502355(min)22(min)E7452013722(min)F8563102825G107853201035 從上表來看，應(yīng)選擇D作為學(xué)校的地址，這樣最遠的居民區(qū)離學(xué)校的距離也只有500米.在現(xiàn)實生活中，同一網(wǎng)絡(luò)中的各點要求提供的服務(wù)的數(shù)量也不盡 相同。我們將各點要求提供的服務(wù)數(shù)量作為該點的權(quán)數(shù)，重新考慮選址問題。例5 在例4中，若七個區(qū)的學(xué)生人數(shù)分別為40、25、45、30、20、35、50人，試問教育部門應(yīng)將學(xué)校建在哪個居民區(qū)，才能使大家都方便？ 所以應(yīng)選擇E作為新建學(xué)校的地址。ABCDEFGA0751801501402805001325B12001356080175350920C1607501501002104001095D20050225040105250870E28010022560035150850