網(wǎng)絡(luò)優(yōu)化第5章最短路問題(編輯修改稿)
2025-06-18 04:41 本頁面
【文章內(nèi)容簡介】 {m in 444 iii wuu ?? ?}{m in 555 iii wuu ?? ?16 最短路算法 算法通過不斷修改這些標(biāo)號，進(jìn)行迭代計(jì)算 . 當(dāng)算法結(jié)束時(shí)，距離標(biāo)號表示的是從起點(diǎn)到該頂點(diǎn)的最短路長度 . 基本思想：對于 V 中每一個(gè)頂點(diǎn) j，賦予兩個(gè)數(shù)值（通常稱為 “ 標(biāo)號 ” ）： 一個(gè)是距離標(biāo)號 uj ，記錄的是從起點(diǎn)到該頂點(diǎn)的最短路長度的上界； 另一個(gè)是前趨標(biāo)號 pred（ j），記錄的是當(dāng)起點(diǎn) s到該頂點(diǎn) j 的一條路長取到該上界時(shí)，該條路中頂點(diǎn) j 前面的那個(gè)直接前趨（節(jié)點(diǎn)） . 迭代進(jìn)行計(jì)算的過程中，所有頂點(diǎn)實(shí)際上被分成了兩類： 一類是離起點(diǎn) s 較近的頂點(diǎn)，它們的距離標(biāo)號表示的是從點(diǎn) s到該頂點(diǎn)的最短路長度，因此其標(biāo)號不會在以后的迭代中再被改變（稱為永久標(biāo)號）； 一類是離起點(diǎn) s 較遠(yuǎn)的頂點(diǎn)，它們的距離標(biāo)號表示的只是從點(diǎn)到該頂點(diǎn)的最短路長度的上界，因此其標(biāo)號還可能會在以后的迭代中再被改變（稱為臨時(shí)標(biāo)號） . 正費(fèi)用網(wǎng)絡(luò) (Dijkstra,1959) 17 正費(fèi)用網(wǎng)絡(luò)（ Dijkstra算法） STEP1. 如果 S=V, 則 uj為節(jié)點(diǎn) s到節(jié)點(diǎn) j的最短路路長 (最短路可以通過數(shù)組 pred所記錄的信息反向追蹤獲得 ), 結(jié)束 . 否則繼續(xù)STEP2. STEP0. (初始化 ) 令 S= ， =V， ；對 V 中的頂點(diǎn) j(j s)令初始距離標(biāo)號 . ? S 0)(,01 ??? sp r e duu s???juSTEP2. 從 中找到距離標(biāo)號最小的節(jié)點(diǎn) i，把它從 刪除，加入 S. 對于所有從 i出發(fā)的弧 , 若 ，則令 . 轉(zhuǎn) STEP1. S SAji ?),( ijij wuu ??ijp r e dwuu ijij ??? )(,18 正費(fèi)用網(wǎng)絡(luò)（ Dijkstra算法） 歸納法 . 算法開始時(shí)結(jié)論成立 . 設(shè)直到迭代的第 k步 ， 上述結(jié)論 (1)(2)成立 . pred(j) pred(i) i j s P1 P2 S S 中具有最小標(biāo)號的頂點(diǎn) i 可以移入 S中 ， 這不會破壞結(jié)論 （ 1） . S引理 在上述 Dijkstra 算法中 , （ 1） 對于 S中的任一頂點(diǎn) j， 其距離標(biāo)號 uj是從起點(diǎn) s到該頂點(diǎn) j 的最短路路長； （ 2） 對于 中的任一頂點(diǎn) j， 其距離標(biāo)號 uj是從起點(diǎn) s出發(fā) ， 只經(jīng)過 S中的頂點(diǎn)到達(dá)頂點(diǎn) j 的最短路路長 . S對于 中的其它頂點(diǎn) k， 修改標(biāo)號 ， 不會破壞結(jié)論 （ 2） . S19 Dijkstra算法 計(jì)算復(fù)雜性分析 對于節(jié)點(diǎn)尋找過程 ， 第一次循環(huán)時(shí)需要 n次比較操作 ， 第二次循環(huán)時(shí)需要 n1次比較操作 ， … ， 依次類推 . 因此 ， 節(jié)點(diǎn)尋找過程的復(fù)雜度為 綜上所述 ， 該算法的復(fù)雜度為 該 算法的主要計(jì)算量在于 STEP2循環(huán) （ 最多執(zhí)行 n次 ） ， 它包括兩個(gè)過程：節(jié)點(diǎn)尋找過程 （ 從 中找到距離標(biāo)號最小的節(jié)點(diǎn) i）和距離修改過程 （ 修改與節(jié)點(diǎn) i相鄰的節(jié)點(diǎn)的距離標(biāo)號 ） . S)(1)1( 2nOnn ????? ?對于距離修改過程 ， 注意到一個(gè)頂點(diǎn)只有當(dāng)它與頂點(diǎn) i相鄰時(shí) ， 其標(biāo)號才可能變更 ， 才需要修改標(biāo)號 . 每次循環(huán)所需要修改標(biāo)號的頂點(diǎn)個(gè)數(shù)最多為 這一過程的整體效應(yīng)相當(dāng)于對每條弧進(jìn)行一次檢查 ， 所以該過程的總計(jì)算復(fù)雜度為 O（ m） . )(id?)()( 22 nOmnO ??對于稠密網(wǎng)絡(luò) ， 這是求解最短路問題可能達(dá)到的最小的復(fù)雜度 ,因?yàn)槿魏嗡惴ǘ贾辽俦仨殞γ織l弧考慮一次 . 對于稀疏網(wǎng)絡(luò) ， 利用各種形式的堆 （ Heap） ， 其復(fù)雜度可以降為 或 等 )l o g(),l o g( nnmOnmO ? ))lo g (( CnmO ?20 標(biāo)號算法（ Labeling Algorithm） 標(biāo)號算法 ：目的就是在算法結(jié)束時(shí)將所有臨時(shí)標(biāo)號轉(zhuǎn)變?yōu)橛谰脴?biāo)號 . 無圈網(wǎng)絡(luò)的最短路算法，也可以看成是一種標(biāo)號算法 . 標(biāo)號設(shè)定算法（ LabelSetting Algorithm） ：在通過迭代過程對標(biāo)號進(jìn)行逐步修正的過程中，每次迭代將一個(gè)頂點(diǎn)從臨時(shí)標(biāo)號集合中移入永久標(biāo)號集合中 . 一般只能用來求解 無圈網(wǎng)絡(luò) 和 正費(fèi)用網(wǎng)絡(luò) 的最短路問題 . 標(biāo)號修正算法（ LabelCorrecting Algorithm） ：每次迭代時(shí)并不一定將任何頂點(diǎn)標(biāo)號從臨時(shí)標(biāo)號轉(zhuǎn)變?yōu)橛谰脴?biāo)號，只是對臨時(shí)標(biāo)號進(jìn)行一次修正，所有頂點(diǎn)標(biāo)號仍然都是臨時(shí)標(biāo)號； 只有在所有迭代終止時(shí)，所有頂點(diǎn)標(biāo)號同時(shí)轉(zhuǎn)變?yōu)橛谰脴?biāo)號 . 標(biāo)號設(shè)定算法可以看成是標(biāo)號修正算法的特例，因?yàn)樵谒惴ńK止之前，任何永久標(biāo)號都可以看成是一種特殊的臨時(shí)標(biāo)號 . 對于 一般費(fèi)用網(wǎng)絡(luò) 的最短路問題采用 . 21 一般費(fèi)用網(wǎng)絡(luò)：標(biāo)號修正算法 (逐次逼近法， Successive Approximation) Bellman Ford算法 (Ford,1956) 歸納法 計(jì)算從起點(diǎn)到所有其它頂點(diǎn)的最短路 : 相當(dāng)于迭代法解 Bellman方程
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1