【正文】 5 分析 (Analysis) 擴展 (Extension) 加速 (Speed up) 應(yīng)用 (Application) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 24 / 70 擴展 (Extension) 針對不同問題的物理意義，通過擴展 Dijkstra算法來達到求解目的。 這個算法的復(fù)雜度是多少？ 仍然是 O(n2)。給定源點 s，求從 s出發(fā)到其他頂點的最大通過率路徑。 怎樣實現(xiàn)？ 修改 update函數(shù)。求從 s出發(fā)到其他頂點的帶寬大于 C的最小權(quán)重路徑。 Project 給出求解帶寬約束最短路問題的代碼。求從 s出發(fā)到 d的一對路徑（兩條），要求這兩條路徑“鏈路分離”，且路徑權(quán)重之和最小。 b s c d 4 4 1 1 1 算法不完備。 Dial實現(xiàn) A*算法 雙向 Dijkstra算法 Dijkstra算法加速 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 31 / 70 Dial實現(xiàn) 通過降低 FindMin的復(fù)雜度來加速 目的 Bucket(k) = { i ? i ? V, d(i) = k } 方法 令 C表示最大的權(quán)重，則距離標記最大為 nC。 p(j) = NULL。 Update(s)。 END WHILE Step S d(a), p(a) d(b), p(b) d(c), p(c) d(d), p(d) d(e), p(e) 0 1 2 3 4 5 s sa sae saed saedb saedbc 2, s 2, s ? 6, a 6, a 6, a 6, a ? ? ? 6, d 6, d 6, d ? 4, a 4, a 4, a 4, s 3, a 3, a 6,a 4,a 3,a 6,d ? ? 0 1 2 3 4 5 6 7 ?= nC = 24 a b c d e a e b d e c 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 實現(xiàn)細節(jié)提示 (1/2) 33 / 70 Dial算法實現(xiàn)難點 難點 1：基于桶的 FindMin 難點 2：桶的更新 //桶的實現(xiàn)： mapint,mapint, CVertex* mapBuckets。該 map代表所有的桶。 Hint 2 Hint 3 Update時，如果某個頂點的距離標記從 x變到了 y，先根據(jù) x查找 mapBuckets，再 根據(jù)其 ID定位到它在內(nèi)層 map中的位置， 然后 取出 該頂點。 Dial實現(xiàn) A*算法 雙向 Dijkstra算法 Dijkstra算法加速 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 36 / 70 反向 Dijkstra算法 反向最短路問題 給定宿點 d，求從其他頂點出發(fā)到 d的最短路徑。 目的 交替地從 V – SF 和 V – SB 中選擇頂點進行永久標記，直至 SF和 SB存在相同點 w時停止。 e(u,v)表示從頂點 u到 v的一條有向邊。 難點 3：拼湊和比較。 Hint 2 CVertex中要記錄兩個方向 的 距離 和前繼。 對這個 listCPath*排序，然后輸出第一個元素。 研究性 Project的要求 研究性 Project No. R1 下面兩項任選一項： A）對比 /定量研究 Dijkstra算法和 Dial算法的性能。 Dial實現(xiàn) A*算法 雙向 Dijkstra算法 Dijkstra算法加速 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 41 / 70 A*算法 (1/2) 同樣是針對單源單宿最短路問題，采用特定的頂點距離標記方法來減少不必要的永久標記點。 說明： 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) A*算法 (2/2) 42 / 70 為什么 A*等效于更改權(quán)重后的 Dijkstra？ a s b h(b) w1 d w2 h(s) h(a) w1’=w1+h(a) – h(s) w2’=w2+h(b) – h(a) d’(b)=w1’+w2’ =w1+w2+h(b) – h(s) =d(b)+h(b) – h(s) 與 A*要求的距離標記只差一 個常量 ( – h(s) )。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 46 / 70 鏈路狀態(tài)協(xié)議 發(fā)布者 1 序號 時間 2 2 3 4 4 22 發(fā)布者 2 序號 時間 1 2 3 1 4 6 發(fā)布者 3 序號 時間 1 4 2 1 4 1 5 4 發(fā)布者 4 序號 時間 1 22 2 6 3 1 5 10 6 5 發(fā)布者 5 序號 時間 3 4 4 10 6 3 發(fā)布者 6 序號 時間 4 5 5 3 2 1 3 4 5 6 4 3 5 6 1 1 4 2 10 22 A B I J C D E F G 鏈路狀態(tài)信息的產(chǎn)生 鏈路狀態(tài)信息的洪泛 拓撲圖的構(gòu)造 X A B C D 鏈路狀態(tài)更新是定時的，或檢測到變化。因為最短路的子路徑必然也是最短路。 如果 A知道，會有什么不一樣？ 但是，鏈路狀態(tài)協(xié)議就是為了保證不會出現(xiàn)這種情況。 最典型的例子就是鏈路失效。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 48 / 70 最短路算法 1 2 LabelSetting算法 LabelCorrecting算法 Dijkstra算法只適用于正權(quán)重圖，針對具有負權(quán)重（甚至負圈）的圖，該怎么辦？ 3 AllPair最短路算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 49 / 70 LabelCorrecting算法 負權(quán)重 1 2 3 4 一般的 LabelCorrecting BellmanFord算法 應(yīng)用 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 50 / 70 負權(quán)重 Dijkstra算法為什么只能用于非負權(quán)重的圖？ 之所以 FindMin得到的頂點可以被永久標記，因為該頂點的距離不可能被改進了。 怎么辦？能否找到一個算法，可在任意權(quán)重的圖中求最短路。 工程中，一般用 Dijkstra算法（因為它快）；當(dāng)出現(xiàn)負權(quán)重時，用BellmanFord算法。所有頂點的距離標記就是最短路距離值的充要條件是： 對所有的邊 e(i,j)，都有 d(j) ? d(i) + we(i,j) 算法設(shè)計 檢查圖中邊 e(i, j)，若它不滿足最優(yōu)性條件，就更新其距離標記： d(j) = d(i) + we(i,j) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最優(yōu)性條件 54 / 70 最優(yōu)性條件 令 d(j)表示源點 s到頂點 j的距離標記。 充分性： 如果所有距離標記都滿足上述條件，那么它們就是最短路的距離。 END FOR d(s) = 0。 END WHILE 分析 負圈 實現(xiàn) 正確性： 該算法 可在 有限步驟內(nèi)收斂到最佳解。 況且： 就沒有復(fù)雜度更低的實現(xiàn)方法了么？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 56 / 70 LabelCorrecting算法 負權(quán)重 1 2 3 4 一般的 LabelCorrecting BellmanFord算法 應(yīng)用 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 57 / 70 FIFO實現(xiàn) (BellmanFord) 算法描述 ? 算法由 n次循環(huán)構(gòu)成。除非存在負圈。除非存在負圈。 k=1 第一次循環(huán)(k=1)后，具有最短路跳數(shù)為 1的那些頂點的距離標記會被更新為最佳值么？ YES， OF COURSE k?k+1 假定第 k次循環(huán)后，所有具有最短路跳數(shù)小于等于 k的那些頂點標記都被更新為最佳值了。 2第三輪呢？ 所有頂點都沒有更新。 d(s) = 0。 p(j) = i。 ? 只要能檢測出某一輪中沒有更新距離標記，就可以終止循環(huán)。 只要 i 的鄰接點不斷地告訴 i 它們到其它目的點的距離發(fā)生了怎樣的變化， i 就可以據(jù)此計算它到網(wǎng)絡(luò)中其它點怎么走最短。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 62 / 70 最短路算法 1 2 LabelSetting算法 LabelCorrecting算法 Dijkstra算法和 BellmanFord算法解決的是單源最短路問題。 選哪個最短路算法好？ 當(dāng)然是 Dijkstra好啰，因為它快嘛。 ? 在新圖上，從其它頂點出發(fā)分別調(diào)用 1次 Dijkstra算法。 FOR all vertex i in V DO d(i,i) = 0。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 復(fù)雜度分析 66 / 70 復(fù)雜度？ 假定權(quán)重為整數(shù)，且最大值為 C。 復(fù)雜度： O(n3C) 若放棄整數(shù)假設(shè)，證明方法不同，但結(jié)論一樣。 dk(i,j) 假如只準經(jīng)過前 k–1 個頂點的話，頂點 i 和 j 之間的最短路距離。 遞推 dk+1(i,j) = min{ dk(i,j), dk(i,k) + dk(k,j) } Floyd_Warshall(G(V, E)) FOR all vertex i and j in V DO d(i,j) = ?。 p(i,j) =