最短路問題（課堂PPT）

1、1最短路問題2最短路徑問題的實例n搬家公司的最短路徑安排某搬家公司負責(zé)一戶人家的搬家業(yè)務(wù)，從出發(fā)點V1到新居V7之間的各段路徑距離如下圖所示（單位：km）。請問搬家公司如何安排路徑，使運輸距離最短？V3V2V4V5V6V1V7515537464876賦權(quán)有向圖23求解算法-Dijkstra算法n基本原理：最短路的子路也是最短路。V2V3V429844V1易知v1到v4的最短路徑為v1-v2-v3-v4，最短距離10則v1到v3的最短路徑肯定為v1-v2-v3同樣v1到v2的最短路肯定為v1-v24實例的Dijkstra算法求解步驟n(1)從起點v1出發(fā)，易知v1到v1的最短距離L11=0，對v

2、1標號0V3V2V4V5V6V1V7515537464876205n(2)找出同v1相鄰的未標號的點有v2,v3,v4，求出從v1到其所有相鄰點的距離(v1-v2:5;v1-v3:4;v1-v4:7)，距離最短路徑為v1-v3，最短距離為L13=4，將v3標記為4V3V2V4V5V6V1V75155374648762046n(3)找出所有與v1,v3相鄰的未標記的點v2,v4,v5，求出從v1直接到這些點的距離(v1-v2:5;v1-v4:7)以及經(jīng)過v3到這些點的距離(v1-v3-v4:6;v1-v3-v5:12;)找出這些距離中最短路徑為v1-v2，最短距離為L12=5，將v2標記為5V3

3、V2V4V5V6V1V751553746487620457n(4)找出所有與v1,v2,v3相鄰的未標記的點v4,v5,v6，求出從v1直接到這些點的距離(v1-v4:7)以及經(jīng)過v2到這些點的距離(v1-v2-v4:11;v1-v2-v5:10;v1-v2-v6:8)以及經(jīng)過v3到這些點的距離(v1-v3-v4:6;v1-v3-v5:12)找出這些距離中最短的路徑為v1-v3-v4，最短距離為L14=6，將v4標記為6V3V2V4V5V6V1V7515537464876204568n(5)找出所有與v1,v2,v3,v4相鄰的未標記的點v5,v6，求出從v1經(jīng)過v2到這些點的距離(v1-v2

4、-v5:10;v1-v2-v6:8)以及經(jīng)過v3到這些點的距離(v1-v3-v5:12)以及經(jīng)過v4到這些點的距離(v1-v4-v5:13;v1-v4-v6:11)找出這些距離中最短的路徑為v1-v2-v6，最短距離為L16=8，將v6標記為8V3V2V4V5V6V1V75155374648762045689n(6)找出所有與v1,v2,v3,v4,v6相鄰的未標記的點v5,v7，求出從v1經(jīng)過v2到這些點的距離(v1-v2-v5:10)以及經(jīng)過v3到這些點的距離(v1-v3-v5:12)以及經(jīng)過v4到這些點的距離(v1-v4-v5:13)以及經(jīng)過v6到這些點的距離(v1-v2-v6-v5:9

5、;v1-v2-v6-v7:14)找出這些距離中最短的路徑為v1-v2-v6-v5，最短距離為L15=9，將v5標記為9V3V2V4V5V6V1V7515537464876204568910n(7)找出所有與v1,v2,v3,v4,v5,v6相鄰的未標記的點v7，求出從v1經(jīng)過v5到這些點的距離(v1-v2-v6-v5-v7:13)以及經(jīng)過v6到這些點的距離(v1-v2-v6-v7:14)找出這些距離中最短的路徑為v1-v2-v6-v5-v7，最短距離為L15=13，將v7標記為13。至此所有點都已標記，即求出了v1到所有其他點的最短路徑V3V2V4V5V6V1V7515537464876204

6、56891311Dijkstra算法練習(xí)求如圖所示的從v1到其他點的最短路徑及路長.3273221v1v2v3v5v6v43612搬家公司最短路徑問題的數(shù)學(xué)模型n決策變量：圖中每條邊最短路是否經(jīng)過12f13f14f24f25f26f34f35f45f46f57f67f1V0Vijf（經(jīng)過( i,Vj）這條?。ㄎ唇?jīng)過( i,Vj）這條?。?5f13n目標函數(shù)：經(jīng)過的距離最短121367min54.6zfff約束條件：從v1出去的邊只能有一條：1213141fff到達v7的邊只能有一條：57670-1ff（）進出其他頂點的邊數(shù)量相等：242526120ffff3435130fff45461424

7、34()0fffff5725354565(+)0fffff67652646()0ffff0-1約束：01ijf 或14求解結(jié)果V3V4V5V6V1V7515537464876V2最短距離：13km15最短路問題的一般化數(shù)學(xué)模型n在賦權(quán)有向圖D=(V,A)中，尋求從始點 到終點 的最短路問題，假設(shè)邊 的權(quán)重為 。可以設(shè)決策變量為圖中邊 是否經(jīng)過 的0-1變量，此時，最短路問題可轉(zhuǎn)化為如下0-1整數(shù)規(guī)劃問題。( ,)ijv vsvtvijf(,):minijijijv vAPzf( ,)ijv vij01,( ,)1,0,1,ijijijjiijjiijjifv vAffisffis tffit

8、或s.t.始點的流出量-流入量=1終點的流出量-流入量=-1其他點的流出量-流入量=016賦權(quán)無向圖的最短路徑問題V3V2V4V5V6V1V7515537464876賦權(quán)無向圖17數(shù)學(xué)模型43f42f56f12f13f14f24f25f26f34f35f45f46f57f67f1V0Vijf（經(jīng)過( i,Vj）這條?。ㄎ唇?jīng)過( i,Vj）這條?。?5f決策變量：圖中每條邊最短路是否經(jīng)過52f53f54f62f64f18數(shù)學(xué)模型(,):minijijijv vAPzfs.t.始點的流出量-流入量=1終點的流出量-流入量=-1其他點的流出量-流入量=001,( ,)1,0,1,ijijijjii

9、jjiijjifv vAffisffis tffit 或目標函數(shù)：19最短路問題的應(yīng)用n某公司正在研制一種有極好銷售潛力的新產(chǎn)品。當(dāng)研究工作接近完成時，公司獲悉一家競爭者正計劃生產(chǎn)這種產(chǎn)品。要突擊趕制出這種產(chǎn)品以參與競爭，還有四個互不重疊的階段。為了加快進度，每個階段都可采取“優(yōu)先”或“應(yīng)急”的措施。不同的措施下每段工作所需要的時間（月）和費用（百萬元）如小下表示?，F(xiàn)有一千萬元資金供這四個階段使用，則每段應(yīng)采取什么措施能使這種產(chǎn)品盡早上市。試將此問題化成最短路問題并求解。20將原問題轉(zhuǎn)化為賦權(quán)有向圖n轉(zhuǎn)化的方法：網(wǎng)絡(luò)結(jié)點編號用一對數(shù)字(i,j)表示，其中i表示各個階段，j表示該階段末剩余資金；

10、結(jié)點(i,j)與結(jié)點(i+1,k)之間的弧的權(quán)數(shù)，表示當(dāng)采取“費用為(j-k)百萬元的措施”時第i+1段的工作所需的時間。設(shè)起點為(0,10)，終點為(4,0)。210,10v11,9v21,8v31,7v45422,72,6v52,5v62,4v73232323,43,33,2v83,1v933355554,34,24,14,0v102222111初始有1千萬第1階段采用正常措施后資金剩余9百萬第1階段采用正常措施所需時間5個月第1階段采用優(yōu)先措施后資金剩余8百萬第1階段采用正常措施所需時間4個月第4階段后資金正好用完3,0322問題的數(shù)學(xué)模型n決策變量：圖中每條弧是否被最短路經(jīng)過12f13f14f25f35f36f46f58f47f68f69f79f910f54f810f10ijifi（經(jīng)過(v ,vj）這條?。ㄎ唇?jīng)過(v ,vj）這條弧）23n目標函數(shù)：經(jīng)過的時間最少1213810910min54. 12zffff約束條件：從v1出去的弧只有一條：12131401fff從v10進入的弧只有一條：8109100-()-1ff其他頂