《圖論模型：最短路》PPT課件

《《圖論模型：最短路》PPT課件》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第六章圖論方法§7.1圖論的基本概念定義1一個(gè)有序二元組（V,E）稱(chēng)為一個(gè)圖，記為G=（V,E），其中①V稱(chēng)為G的頂點(diǎn)集，V≠Φ，V中的元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn)，簡(jiǎn)稱(chēng)點(diǎn)；②E稱(chēng)為G的邊集，其元素稱(chēng)為邊，它連接V中的兩個(gè)點(diǎn)，如果這兩個(gè)點(diǎn)是無(wú)序的，則稱(chēng)該邊為無(wú)向邊；否則，稱(chēng)為有向邊。如果V＝｛v1,v2,…,vn}是有限非空點(diǎn)集，則稱(chēng)G為有限圖或n階圖。如果G的每條邊都是無(wú)向邊，則稱(chēng)G為無(wú)向圖；如果G的每條邊都是有向邊，則稱(chēng)G為有向圖。否則稱(chēng)G為混合圖。并且常記E＝{e1,e2,…,em},(ek=vivj,i,j=1,2

2、,…,n),對(duì)于一個(gè)圖G=（V,E），人們通常用一個(gè)圖形來(lái)表示，稱(chēng)其為圖解。凡是有向圖，在圖解上用箭頭標(biāo)明其方向。則G＝（V,E）是一個(gè)有4個(gè)頂點(diǎn)、6條邊的圖，其圖解如下圖：一個(gè)圖會(huì)有許多外形不同的圖解，如上圖。稱(chēng)點(diǎn)vi,vj為邊vivj的端點(diǎn)。在有向圖中，稱(chēng)點(diǎn)vi,vj分別為有向邊vivj的始點(diǎn)和終點(diǎn)；稱(chēng)邊vivj為點(diǎn)vi的出邊，為點(diǎn)vj入邊。由邊連接的兩個(gè)點(diǎn)稱(chēng)為相鄰的點(diǎn)；有一個(gè)公共端點(diǎn)的邊稱(chēng)為相鄰邊；邊和它的端點(diǎn)稱(chēng)為互相關(guān)聯(lián)。常用d(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目，d(v)稱(chēng)為頂點(diǎn)v的度數(shù)；用N（v）表

3、示圖G中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合。定義2若將圖G的每條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F(e)，則稱(chēng)F（e）為該邊的權(quán)，并稱(chēng)圖G為賦權(quán)圖，記為G=(V,E,F)。定義3設(shè)G=(V,E)是一個(gè)圖，，則稱(chēng)是G的一個(gè)通路。如果通路中沒(méi)有相同的邊，則稱(chēng)此通路為道路；始點(diǎn)和終點(diǎn)相同的道路稱(chēng)為圈或回路；如果通路中既沒(méi)有相同的邊，又沒(méi)有相同的頂點(diǎn)，則稱(chēng)此通路為路徑，簡(jiǎn)稱(chēng)路。定義4任意兩點(diǎn)都有通路的圖稱(chēng)為連通圖。定義5連通而無(wú)圈的圖稱(chēng)為樹(shù)，常用T表示樹(shù)?！?.2最短路模型及其算法最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最為廣泛的問(wèn)題之一，不少優(yōu)化問(wèn)題可

4、化為這個(gè)模型。如管道的鋪設(shè)、運(yùn)輸網(wǎng)絡(luò)的設(shè)計(jì)、線(xiàn)路安排、設(shè)備更新、廠(chǎng)區(qū)布局等。定義1設(shè)P（u,v）是賦權(quán)圖G=(V,E,F)中從點(diǎn)u到點(diǎn)v的路徑，用E(P)表示路徑P(u,v)的全部邊的集合，記為，，則稱(chēng)F(P)為路徑P(u,v)的權(quán)或長(zhǎng)度。定義2若P0(u,v)是G中連接u,v的路徑，且對(duì)任意在G中連接u,v的路徑P(u,v)，都有F(P0)≤F(P),則稱(chēng)P0(u,v)是G中連接u,v的最短路徑。根據(jù)上述定理，著名計(jì)算機(jī)專(zhuān)家狄克斯特拉（Dijkstra）給出了求G中某一點(diǎn)到其他各點(diǎn)最短路徑的算法——標(biāo)號(hào)法：T標(biāo)

5、號(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)。凡沒(méi)有得到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é)束。其具體步驟如下：（1）賦初值：給起點(diǎn)v0以P標(biāo)號(hào)，P(v0)＝0，其余各點(diǎn)vi均為T(mén)標(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，邊vivj∈E，且vj為T(mén)標(biāo)

6、號(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最短路權(quán)027136911父點(diǎn)v0v0v5v0

7、v1v4V2v4例2(設(shè)備更新問(wèn)題)某企業(yè)使用一種設(shè)備,每年年初,企業(yè)都要作出決定,如果要繼續(xù)使用舊的,;若購(gòu)買(mǎi)一臺(tái)新設(shè)備,要付購(gòu)買(mǎi)費(fèi).使制定一個(gè)5年更新計(jì)劃,使總費(fèi)用最少?已知設(shè)備每年年初的購(gòu)買(mǎi)費(fèi)分別為:11,11,12,12,13,使用不同時(shí)間設(shè)備所需的維修費(fèi)為:解：設(shè)bi表示設(shè)備在第i年年初的購(gòu)買(mǎi)費(fèi)，ci表示設(shè)備使用i年后的維修費(fèi)，把這個(gè)問(wèn)題化為求有向賦權(quán)圖G=（V,E,F）中的最短路問(wèn)題。設(shè)備年齡0—11—22－33—44—5維修費(fèi)5681118賦權(quán)圖如上圖所示，這樣設(shè)備更新問(wèn)題就變?yōu)椋簭膙1到v6的最短

8、路問(wèn)題。由狄克斯特拉（Dijkstra）算法列表如下：迭代次數(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為兩條最短路徑，路長(zhǎng)