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

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

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

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

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

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

6、路權(quán)027136911父點(diǎn)v0v0v5v0v1v4V2v4 例2(設(shè)備更新問題)某企業(yè)使用一種設(shè)備,每年年初,企業(yè)都要作出決定,如果要繼續(xù)使用舊的, ;若購買一臺(tái)新設(shè)備,要付購買費(fèi).使制定一個(gè)5年更新計(jì)劃,使總費(fèi)用最少?已知設(shè)備每年年初的購買費(fèi)分別為:11,11,12,12,13,使用不同時(shí)間設(shè)備所需的維修費(fèi)為:解：設(shè)bi表示設(shè)備在第i年年初的購買費(fèi)，ci表示設(shè)備使用 i年后的維修費(fèi)，把這個(gè)問題化為求有向賦權(quán)圖G=（V,E,F）中的最短路問題。設(shè)備年齡0112233445維修費(fèi)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)號(hào)10+V121622304159V2322304157V34304153V454153V5653V6最短路權(quán)01622304153父點(diǎn)V1V1V1V1V1V3或v4 計(jì)算結(jié)果表明：路徑v1v3v6或v1v4v6為兩條最短路徑，路長均為53。即第1年、第3年個(gè)購買一臺(tái)新設(shè)備，或第1年、第4年各購買一臺(tái)新設(shè)備為最優(yōu)決策。最小費(fèi)用為53.例3 如下圖表示某區(qū)域的交通網(wǎng)絡(luò)，各條旁邊所注的數(shù)字表示通過該公路所估計(jì)行駛的時(shí)間（單位：小時(shí)）。試問S到T估計(jì)至少要行駛多少小時(shí)？并寫出最短路徑。解：狄克斯特拉（Dijkstra

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

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