1、運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,最短路問(wèn)題,有些問(wèn)題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問(wèn)題，也可以歸結(jié)為求最短路的問(wèn)題。因此這類(lèi)問(wèn)題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。,求最短路有兩種算法，一是求從某一點(diǎn)至其它各點(diǎn)之間最短離的狄克斯屈拉(Dijkstra)算法；另一種是求網(wǎng)圖上任意兩點(diǎn)之間最短的矩陣算法。,最短路問(wèn)題，就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路 .,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,渡河問(wèn)題,一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過(guò)河到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼

2、就要吃羊，羊就要吃白菜，問(wèn)應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過(guò)河去，并且在河上來(lái)回次數(shù)最少？這個(gè)問(wèn)題就可以用求最短路方法解決。,設(shè)：M人 W狼 S羊 V白菜,渡河方案共有10種，構(gòu)造如下一個(gè)圖，每條邊的距離為1，問(wèn)題變?yōu)榍笠粭l從MWSV到的最短路。,北岸,南岸,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法,點(diǎn)標(biāo)號(hào)：b(j) 起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng)；,邊標(biāo)號(hào)：k(i，j)=b(i)+dij，,步驟：1.令起點(diǎn)的標(biāo)號(hào)；b(s)0。,先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點(diǎn)是vs,終點(diǎn)是vt ,以vi為起點(diǎn)vj為終點(diǎn)的弧記為（i，j）,距離為dij,2.找出所

3、有vi已標(biāo)號(hào)vj未標(biāo)號(hào)的弧集合 B= （i，j） 如 果這樣的弧不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；,3.計(jì)算集合B中弧k(i，j)=b(i)+dij的標(biāo)號(hào),4.選一個(gè)點(diǎn)標(biāo)號(hào) 返回到第2步。,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,【例】求下圖v1到v7的最短路長(zhǎng)及最短路線,0,8,6,2,2,5,4,4,11,14,7,5,10,7,12,11,v7已標(biāo)號(hào)，計(jì)算結(jié)束。從v1到v7的最短路長(zhǎng)是 11,最短路線是：v1 v4 v6 v7,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出vs到任意點(diǎn)的最短路線，如果

4、某個(gè)點(diǎn)vj不能標(biāo)號(hào)，說(shuō)明vs不可達(dá)vj .,無(wú)向圖最短路的求法,無(wú)向圖最短路的求法只將上述步驟2改動(dòng)一下即可。,點(diǎn)標(biāo)號(hào)：b(i) 起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng)；,邊標(biāo)號(hào)：k(i，j)=b(i)+dij，,步驟：1.令起點(diǎn)的標(biāo)號(hào)；b(s)0。,3.計(jì)算集合B中邊標(biāo)號(hào)：ki，j=b(i)+dij,4.選一個(gè)點(diǎn)標(biāo)號(hào): 返回到第2步。,2.找出所有一端vi已標(biāo)號(hào)另一端vj未標(biāo)號(hào)的邊集合 B= i，j 如果這樣的邊不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,【例】求下圖v1到各點(diǎn)的最短路及最短距離,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,

5、12,24,8,24,18,所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是v1到該點(diǎn)的最短距離，最短路線就是紅色的鏈。,進(jìn)入演示和練習(xí),運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,有負(fù)權(quán)的最短路算法,假設(shè)圖中沒(méi)有負(fù)回路。如下圖是一條負(fù)回路，最短路權(quán)無(wú)下界。,當(dāng)vi到vj之間沒(méi)有弧連接時(shí)，令wij,列表迭代計(jì)算：,設(shè)vs到vj經(jīng)過(guò)vi到達(dá)vj，則vs到vj的最短距離為：,迭代：,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,【例】求下圖v1到v8的最短路長(zhǎng)及最短路線,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,5,2,7,1,1,5,0,5,2,7,3,1,5,6,0,5,2,7,3,1,5,6,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,*任意兩點(diǎn)間最短距離的矩陣算法*（選講）,【例】在下圖中用矩陣計(jì)算法求各點(diǎn)之間的最短距離,【解】定義dij為圖中兩相鄰點(diǎn)的距離，若i與j不相鄰，令dij=。則,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,步驟:1.,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,應(yīng)用（教材P270例4）,16,16,17,17,18,22,30,41,59,22,30,41,23,31,23,最優(yōu)更新方案：1.第一年和第三年購(gòu)置新設(shè)備；2.第一年和第四年購(gòu)置新設(shè)備。總費(fèi)用為53。,運(yùn)籌學(xué) 北京郵電大學(xué),2020/8/6,最大流問(wèn)題,作業(yè)：教材P2