運(yùn)籌學(xué)第06章圖論概述(編輯修改稿)
2025-06-19 22:15 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 P( )+ lij T( ) 0 ∞ ∞ ∞ ∞ ∞ 0+5 0+8 0+∞ 0+∞ 0+∞ 5 8 ∞ ∞ ∞ 5+∞ 5+3 5+9 5+∞ 8 8 14 ∞ 8+∞ 8+4 8+∞ 8 12 ∞ 8+3 8+9 11 17 11+5 16 1 2 3 4 5 示例 () s a b c d t 5 8 3 9 1 4 9 5 4 3 海斯算法 (1) ?該算法有兩個(gè)依據(jù) ?從 v1 到 vn 的最短路線也是從 vn 到 v1 的最短路線 ?對(duì)于無(wú)向圖必定成立 ?對(duì)于有向圖而言， vn 到 v1 的最短路線是指將圖中弧的方向反過(guò)來(lái)，但權(quán)值不變時(shí)的最短路線 ?若從 vi 到 vj 的最短路線經(jīng)過(guò) vk ，則 vi 到 vk 、 vk 到vj 的都是相應(yīng)的最優(yōu)路線 ?第一條依據(jù)保證了從 vi 到 vj 的最短路線也是從 vj 到 vi 的最短路線 ?則根據(jù)動(dòng)態(tài)規(guī)劃最優(yōu)性原理， vk 到 vj 和 vk 到 vi都是相應(yīng)的最優(yōu)路線，由此得到上面的結(jié)論 海斯算法 (2) ?算法步驟 ?已知網(wǎng)絡(luò)的距離矩陣 L=(lij)， lij表示 vi到 vj的弧上的距離權(quán)值 ?令 dij(0)= lij， i=1～ n， j=1～ n ?dij(t)表示從 vi到 vj的 2t步距離 ?當(dāng) dij(m1)已知時(shí)，令 dij(m)=min{dik(m1)+dkj(m1)| k=1～ n} ?當(dāng)對(duì)所有的 i, j有 dij(m)=dij(m1)時(shí)， dij(m)是 vi到 vj的最短距離。否則，若 2m1＜ n1， m=m+1，轉(zhuǎn)上一步；若 2m1≥n1，說(shuō)明存在負(fù)初等回路，最短路線不存在，算法停止 海斯算法 (3) ?該算法可以判斷是否存在負(fù)初等回路，適用于任意權(quán)值的賦權(quán)連通有向圖或無(wú)向圖 ?所得的結(jié)果矩陣中包含了圖中任意兩點(diǎn)之間的最短距離 示例 () s a b c d t 5 8 3 9 1 4 9 5 4 3 ?路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長(zhǎng)度，試用 海斯算法 求 s到t的最短路線 示例 () ?????????????????????????????????????????0509301404930850)0(D??????????????????????????????????????????????????????tsssssddssssdccbbsdbabasccacassbasssD0508301594704126340128850)1(示例 () ?????????????????????????????????????????????????????tsssssddsssscccbasbbabascaaaascassssD050830159470411634016118850)2(?????????????????????????????????????????????????????tsssssddsssscccbasbbabasaaaaasssssssD050830159470411634016118850)3(示例 () ?由于 D(3)=D(2)，停止計(jì)算 ?s到 t 的最短路線長(zhǎng)度為 16 ?由 D(2)知 s到 t 經(jīng)過(guò) c ?由 D(1)知 s到 c經(jīng)過(guò) a， c到 t經(jīng)過(guò) d ?則最短路線為 s a c d t s a b c d t 5 8 3 9 1 4 9 5 4 3 福德 (Ford)算法 (1) ?該算法和 Dijkstra算法一樣 有兩個(gè)依據(jù) ?從 v1 到 vn 的最短路線也是從 vn 到 v1 的最短路線 ?對(duì)于無(wú)向圖必定成立 ?對(duì)于有向圖而言， vn 到 v1 的最短路線是指將圖中弧的方向反過(guò)來(lái)，但權(quán)值不變時(shí)的最短路線 ?以 vn 為起點(diǎn)， v1 為終點(diǎn)應(yīng)用動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 ?第一條依據(jù)保證了按這種方法求得的結(jié)果是從 v1 到 vn 的最短路線 福德 (Ford)算法 (2) ?算法步驟 ?已知網(wǎng)絡(luò)的距離矩陣 L=(lij)， lij表示 vi到 vj的弧上的距離權(quán)值 ?令 dj(1)= l1j， j=1～ n ?dj(t)表示從 v1到 vj的步數(shù)不超過(guò) t的最短距離 ?當(dāng) dj(k)已知時(shí)，令 dj(k+1)=min{di(k)+lij| i=1～ n} ?當(dāng)對(duì)所有的 j有 dj(k+1)=dj(k)時(shí)， dj(k)是 v1到 vj的最短距離。否則，若 k＜ n1， k=k+1，轉(zhuǎn)上一步；若k≥n1，說(shuō)明存在負(fù)初等回路，最短路線不存在，算法停止 福德 (Ford)算法 (3) ?該算法可以判斷是否存在負(fù)初等回路，適用于任意權(quán)值的賦權(quán)連通有向圖或無(wú)向圖 ?所得的結(jié)果中包含了從 v1到其他任意點(diǎn)的最短距離 示例 () s a b c d t 5 8 3 9 1 4 9 5 4 3 ?路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長(zhǎng)度，試用 Ford 算法求 s 到 t的最短路線 示例 () ????????? )1()1()1()1()1()1( ,8,5,0 tdcbas dddddd??????? )2()2()2()2()2()2( ,12,8,8,5,0 tdcbas dddddd17,11,8,8,5,0 )3()3()3()3()3()3( ?????? tdcbas dddddd1
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1