應(yīng)用一：最短路問題課件

數(shù)學(xué)建模圖論方法專題

最短路問題

最短路問題

最短路問題是最重要的優(yōu)化問題之一，它不僅可以直接應(yīng)用于解決生產(chǎn)實際的許多問題例如各種管道的鋪設(shè)、線路的安排、廠區(qū)的布局、設(shè)備的更新等等，而且經(jīng)常被作為一個基本工具，用于解決其它優(yōu)化問題如運輸網(wǎng)絡(luò)的最小費用流等。（最短距離、費時最少、費用最?。?quán)、賦權(quán)圖：對圖G的每一條邊e，可賦與一個實數(shù)w（e）稱為邊e的權(quán)。圖G連同它邊上的權(quán)稱為賦權(quán)圖。路中邊權(quán)最小的稱為最短路。權(quán)可以表示鐵路長度，通訊網(wǎng)絡(luò)的造價，網(wǎng)絡(luò)中表示耗時等。定義：設(shè)P(u,v)是加權(quán)圖G中從u到v的路徑,則該路徑上的邊權(quán)之和稱為該路徑的權(quán),記為w(P).從u到v的路徑中權(quán)最小者P*(u,v)稱為u到v的最短路徑.最短路問題在實際工作中應(yīng)用1、通訊網(wǎng)絡(luò)中最可靠問題2、最大容量問題3、統(tǒng)籌方法中求關(guān)鍵路線4、背包問題5、選址問題6、工件加工順序問題7、中國郵遞員問題重要性質(zhì)：若v0v1…vm

是G中從v0到vm的最短路,則對1≤k≤m,v0v1…vk

必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路。固定起點的最短路問題Dijkstra算法

Dijkstra算法是由荷蘭計算機科學(xué)家狄克斯特拉（Dijkstra）于1959年提出的。使用范圍:尋求從一固定頂點v0到其余各點的最短路徑;有向圖、無向圖和混合圖;權(quán)非負(fù).求解思路：從始點出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。

Dijkstra算法——算法步驟S:具有永久標(biāo)號的頂點集;l(v):

v的標(biāo)記,表示從起點v0到v的一條路的權(quán);

z(v):v的父頂點,用以確定最短路徑;兩種標(biāo)號①

P標(biāo)號（Permanent固定/永久性標(biāo)號）

——從始點到該標(biāo)號點的最短路權(quán)②

T標(biāo)號（Temporary臨時性標(biāo)號）

——從始點到該標(biāo)號點的最短路權(quán)上界輸入加權(quán)圖的帶權(quán)鄰接矩陣w=[w(vi,vj)]nxn.初始化：令l(v0)=0,（給起始點v0標(biāo)上固定標(biāo)號）,vv0,l(v)=（其余各點標(biāo)臨時性標(biāo)號）;

S={v0};z(v)=v0更新l(v),

z(v)

尋找不在S中的頂點u（與前一點相鄰接）,使l(u)為最小.把u加入到S中,然后對所有不在S中的頂點v,如l(v)>l(u)+w(u,v),則更新l(v),z(v),即l(v)l(u)+w(u,v),z(v)u;重復(fù)步驟2),直到所有頂點都在S中為止.例1：用Dijkstra算法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421解（1）首先給v1以P標(biāo)號，給其余所有點T標(biāo)號。（2）v1的鄰接點為v2，v3。v1v2v3v4v6v5352242421（4）例1：用Dijkstra算法求下圖從v1到v6的最短路。v2的鄰接點為v3，v4，v5。v1v2v3v4v6v5352242421（5）（6）反向追蹤得v1到v6的最短路為：v3的鄰接點為v5。1,6例2：v5v223464v3v1v41210

61210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6v5v223464v3v1v41210

61210v8v9v72363v60,01,∞1,∞1,11,∞1,∞1,∞1,31,6v5v223464v3v1v41210

61210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31,5v5v223464v3v1v41210

61210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,31,61,5v5v223464v3v1v41210

61210v8v9v72363v60,01,∞4,111,11,∞1,∞1,∞1,33,53,5v5v223464v3v1v41210

61210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞3,5v5v223464v3v1v41210

61210v8v9v72363v60,01,∞4,111,11,∞1,∞1,31,∞3,5v5v223464v3v1v41210

61210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞3,5v5v223464v3v1v41210

61210v8v9v72363v60,04,111,11,∞2,61,∞1,31,∞3,5v5v223464v3v1v41210

61210v8v9v72363v60,05,101,11,∞2,65,121,35,93,5v5v223464v3v1v41210

61210v8v9v72363v60,05,101,11,∞2,65,121,35,9

知從v1到v8的最短路為：

P1，8=P（v1，v3，

v2，

v5，v8）Dijkstra算法的MATLAB實現(xiàn)w=[012inf748inf;1023inf

inf7inf;22015inf

inf

inf;

inf3103inf

inf6;7inf5303inf4;4inf

inf

inf3026;87inf

inf

inf204;

inf

inf

inf64640]l=01236469z=111341641445642537w=[041inf

inf

inf;

inf0inf424;

inf50inf67;

inf

inf

inf0inf

inf;

inf

inf

inf50inf;

inf

inf

inf

inf30];l=04186869z=11122364任意兩點間的最短路問題Floyd算法使用范圍:求每對頂點的最短路徑;有向圖、無向圖和混合圖;算法思想:

直接在圖的帶權(quán)鄰接矩陣中用插入頂點的方法依次遞推地構(gòu)造出n個矩陣D(1),D(2),…,D(v),D(v)是圖的距離矩陣,同時引入一個后繼點矩陣記錄兩點間的最短路徑.輸入?yún)?shù)：G的帶權(quán)鄰接矩陣W.算法輸出：距離矩陣D以及路由矩陣R.（I）求距離矩陣的方法.（II）求路徑矩陣的方法.在建立距離矩陣的同時可建立路徑矩陣R．（III）查找最短路路徑的方法.然后用同樣的方法再分頭查找．若：（IV）Floyd算法：求任意兩頂點間的最短路.例3：求下圖中加權(quán)圖的任意兩點間的距離與路徑.插入點v1，得：矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素.插入點v2，得：矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素.插入點v3，得：插入點v4，得：插入點v5，得：插入點v6，得：故從v5到v2的最短路為8由v6向v5追溯:由v6向v2追溯:所以從到的最短路徑為：a=[01inf

inf

inf2;104inf

inf4;

inf402inf1;

inf

inf2033;

inf

inf

inf305;241350];68－523－374Floyd算法的MATLAB實現(xiàn)a=[0862inf;

inf0-5-3inf;

inf

inf0inf4;

inf

inf

inf0inf;

inf3inf70];

最短路應(yīng)用

設(shè)備更新問題

例：某企業(yè)使用一種設(shè)備，在每年年初，決策者需要決定是否購置新的，還是繼續(xù)使用舊的。若購置新設(shè)備，就要支付一定的購置費用；若繼續(xù)使用舊的，需要支付一定的維修費用?，F(xiàn)在的問題是如何制定一個五年計劃，使總的支付費用最少，表1為設(shè)備在各年年初的價格，表2為使用不同時間的設(shè)備所需要的維修費用。表1設(shè)備的各年價格表2使用不同時間的維修費用年份一二三四五購置費

1111121213使用年限

0~11~22~33~44~5年修理費

5681118解：（1）分析：顯然可以選擇的設(shè)備更新方案是很多的。例如每年都更新一臺新設(shè)備，其購置費用為（11+11+12+12+13）萬元=59萬元，而每年支付的維修費用為5萬元，五年的合計為25萬元，于是五年的支付費用為（59+25）=84萬元。又如可決定在第一，三，五年各購置一臺，這個方案的設(shè)備購置費用為（11+12+13）=36萬元，維修費用為（5+6+5+6+5）=27萬元，五年總費用為63萬元。如何制定計劃適得總的支付費用最少呢？可以把此問題最化為最短路問題。（2）用點vi代表“第i年年初購進(jìn)一臺新設(shè)備”這種狀態(tài)（v6為第5年年底的末狀態(tài)）。?。╲i,vj）表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初。?。╲i

,vj）上的權(quán)數(shù)表示該期間設(shè)備所需的費用.每條弧的權(quán)可按已知資料計算出來。如（v1，v4）是第一年年初購進(jìn)的一臺設(shè)備（支付購置費用為本11萬元），一直使用到了第3年年底（支付維修費用為5+6+8=19萬元），故?。╲1，v4）權(quán)重為30萬元。這樣一來，制定一個最優(yōu)更新計劃的問題就等價于尋求從V1到V6的最短路問題。按求最短路的計算方法（V1，V3，V6）及（V1，V4，V6）均為最短路線，權(quán)重為53萬元。v1v2v3v4v5v6161617171822304159223041233123選址問題1、中心問題所謂中心選址問題就是在一網(wǎng)絡(luò)中選擇一點，建立公用服務(wù)設(shè)施，為該網(wǎng)絡(luò)中的點提供服務(wù)，使得服務(wù)效率最高。比如一個區(qū)域的消防站、自來水廠、學(xué)校、變電站、銀行、商店等選址。為了提高服務(wù)效率，自然的想法是將這些設(shè)施建立在中心地點。要求網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點離服務(wù)設(shè)施的距離盡可能小。設(shè)網(wǎng)絡(luò)N有個n點v1,v2,…,vn。dij表示點vi到vj之間的距離（即最短路的長度），并記dii=0(i=1,2,…,n)。定義1:

記,。若,則稱點vk為網(wǎng)絡(luò)N的中心，I為直徑。定義2:

令，若，則稱vk為網(wǎng)絡(luò)N的中心。例1某城市要建立一個消防站，為該市所屬的七個區(qū)服務(wù)，如圖所示．問應(yīng)設(shè)在哪個區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最距離矩陣第i行的最大值S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處.例2教育部門打算在某新建城區(qū)建一所學(xué)校，讓附近七個居民區(qū)的學(xué)生就近入學(xué)。七個居民區(qū)之間的道路如下圖所示，學(xué)校應(yīng)建在哪個居民區(qū)，才能使大家都方便？（圖中距離單位：百米）。2、重心問題例3例2中，七個居民區(qū)的學(xué)生人數(shù)分別為：40、25、45、30、20、35、50人，學(xué)校應(yīng)建在哪個居民區(qū)，才能使大家都方便？（圖中距離單位：百米）。簡易公路建設(shè)方案

某合同戰(zhàn)術(shù)訓(xùn)練基地為保障即將進(jìn)行的聯(lián)合軍事演習(xí)，準(zhǔn)備在原有的1個油庫的基礎(chǔ)上，再設(shè)立7個固定的燃料補給點。練習(xí)v1v7v6v2v8v5v3v4油庫與補給點的位置如圖所示，其中油庫位于v1點，補給點位于v2,…,v8點。經(jīng)過前期的測繪工作，如果在油庫和補給點之間修建簡易公路，由于地形不同，每段公路花費如圖，每單位費用為1萬元。請根據(jù)測繪結(jié)果，規(guī)劃一個總造價最低的建設(shè)方案。v1v7v6v2v8v5v3v425734326436174182總造價最低各補給點到油庫的花費均達(dá)到最??？v1v7

6v6

4v21v8

9v5

6v32

v432243611簡易公路建設(shè)方案最短運輸路線問題

如圖的交通網(wǎng)絡(luò)，每條弧上的數(shù)字代表車輛在該路段行駛所需的時間，有向邊表示單行道，無向邊表示可雙向行駛。若有一批貨物要從1號頂點運往11號頂點，問運貨車應(yīng)沿哪條線路行駛，才能最快地到達(dá)目的地？

102374116598135122106158879932271→8→9→10→11最廉價航費表的制定

某公司在六個城市c1,…,c6中有分公司，從ci到cj

的直接航程票價記在下述矩陣中的(i,j)位置上。（∞

表示無直接航路），請幫助該公司設(shè)計一張任意兩城

市間的票價最便宜的路線表。運行輸出結(jié)果：

D=035453525103501520302545150102035352010010252530201003510253525350path=