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