圖論模型最短路

圖論模型最短路第1頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月§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,…,n),對(duì)于一個(gè)圖G=（V,E），人們通常用一個(gè)圖形來(lái)表示，稱(chēng)其為圖解。凡是有向圖，在圖解上用箭頭標(biāo)明其方向。第2頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

則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入邊。第3頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

由邊連接的兩個(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）表示圖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ù)。第4頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

§7.2最短路模型及其算法最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最為廣泛的問(wèn)題之一，不少優(yōu)化問(wèn)題可化為這個(gè)模型。如管道的鋪設(shè)、運(yùn)輸網(wǎng)絡(luò)的設(shè)計(jì)、線(xiàn)路安排、設(shè)備更新、廠區(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的最短路徑。第5頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

根據(jù)上述定理，著名計(jì)算機(jī)專(zhuān)家狄克斯特拉（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)。凡沒(méi)有得到P標(biāo)號(hào)的點(diǎn)都標(biāo)有T標(biāo)號(hào)。第6頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

算法每一步是把某一點(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)號(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)，則停止；第7頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

例2求下圖中V0到其余各點(diǎn)的最短路。第8頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

第9頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

第10頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

第11頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

迭代次數(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)v0v0v5v0v1v4V2v4第12頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

第13頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

例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第14頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

賦權(quán)圖如上圖所示，這樣設(shè)備更新問(wèn)題就變?yōu)椋簭膙1到v6的最短路問(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第15頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

計(jì)算結(jié)果表明：路徑v1v3v6或v1v4v6為兩條最短路徑，路長(zhǎng)均為53。即第1年、第3年個(gè)購(gòu)買(mǎi)一臺(tái)新設(shè)備，或第1年、第4年各購(gòu)買(mǎi)一臺(tái)新設(shè)備為最優(yōu)決策。最小費(fèi)用為53.例3如下圖表示某區(qū)域的交通網(wǎng)絡(luò)，各條旁邊所注的數(shù)字表示通過(guò)該公路所估計(jì)行駛的時(shí)間（單位：小時(shí)）。試問(wèn)S到T估計(jì)至少要行駛多少小時(shí)？并寫(xiě)出最短路徑。解：狄克斯特拉（Dijkstra）算法列表如下：第16頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

迭代次數(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+∞V2436359V156357V56657V6767V487D最短路權(quán)03216357父點(diǎn)S

V3V3SV3V3SV1第17頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

最短路模型還可以應(yīng)用于中心選址問(wèn)題。所謂中心選址問(wèn)題就是在一個(gè)網(wǎng)絡(luò)中選擇一點(diǎn)，建立公用服務(wù)設(shè)施，為該網(wǎng)絡(luò)中的客戶(hù)提供服務(wù)，使得服務(wù)效率最高。比如一個(gè)區(qū)域的消防站、自來(lái)水廠、學(xué)校、變電站、銀行商店等選址。為了提高服務(wù)效率，自然的想法是將這些設(shè)施建立在中心地點(diǎn)。對(duì)于規(guī)則的網(wǎng)絡(luò)，例如圓形、矩形等，中心地點(diǎn)是顯而易見(jiàn)的，然而對(duì)于更多的網(wǎng)絡(luò)是不規(guī)則的。應(yīng)此，我們引入兩個(gè)定義。第18頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

例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第19頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

從上表來(lái)看，應(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ù)，重新考慮選址問(wèn)題。例5在例4中，若七個(gè)區(qū)的學(xué)生人數(shù)分別為40、25、45、30、20、35、50人，試問(wèn)教育部門(mén)應(yīng)將學(xué)校建在哪個(gè)居民區(qū)，才能使大家都方便？第20頁(yè)，課件共22頁(yè)，創(chuàng)作于2023年2月

所以應(yīng)選擇E作為新建學(xué)校的地址。ABCDEFGA0751801501402805001325B12001356080175350920C1607501501002104001095D20050225040105250870E28010022560035150850（min）F3201252