【正文】 是否存在不一致性？ 3?1 1?9 3?9 不會的。 D知道該變化，但 A不知道。更新完成以前就可能出現(xiàn)不一致。 失效的快速恢復是前沿課題?！?Algorithms in Java》 3rd ed。 如果要求解必須為簡單路徑，那么該問題是 NP完全問題，與最長路問題一樣難。 BellmanFord算法是 LabelCorrecting算法的一個特例。 最優(yōu)性條件 令 d(j)表示源點 s到頂點 j的距離標記。矛盾。 p(j) = NULL。 p(j) = i。 但是： 總得有個具體的方法吧。 為什么 n次循環(huán)就夠了？為什么第 n次有更新就說明存在負圈？ 1） s到任一其他頂點的最短路徑最多 n?1跳（即經過 n?1條邊）。 上述事實意味著，該算法最多經過 n?1輪循環(huán)就可以保證所有的距離標記都更新為最佳值。 d*(x)表示 s到 x的最短路的距離。 第二輪呢？ 除了 c和 e外，都沒有更新。 p(j) = NULL。 WHILE LIST非空 DO 從 LIST中取出一個頂點 i； FOR i 的所有關聯(lián)邊 DO IF d(j)d(i)+we DO d(j) = d(i) + we。 ? 不需要 n 輪循環(huán)。 反過來， i 到某個目的點 d 的距離何時更新？ 當 i 的正向鄰接點到 d 的距離發(fā)生了更新時。 C?A 距離矢量更新消息 8 CB?A 3 B 5 BA?C A?B C?D 8 C2 CB?C 3 BB?D 5 B C?B D?B 2 C D?C ? 這只是第 1輪； ? 每當路由器發(fā)生了更新，他就將其新的距離矢量發(fā)給他的鄰接點 (注意：不是洪泛 )； ? 直至沒有更新為止。 復雜度？ 假如使用的最短路算法復雜度為 S(n,m,C)，則為 O(nS(n,m,C))。 還因為利用得到的距離標記，可以將邊的權重變換為非負值。所有這些距離標記就是最短路距離值的 充要條件是： 對所有的 i, j, 和 k，都有 d(i,j) ? d(i,k) + d(k,j) All_Pair_Label_Correcting(G(V, E)) FOR all vertex i and j in V DO d(i,j) = ?。 END WHILE 三角操作 測試該不等式并更新 稱為三角操作。 總共多少節(jié)點對？ 最多多少輪？ n2。 因為該算法采用了一種非常聰明的，基于動態(tài)規(guī)劃思想的三角操作方法。 2023年春季 通信網(wǎng)絡理論基礎 FloydWarshall算法 (2/2) 68 / 70 dk(i,j) 假如只準經過前 k–1 個頂點的話，頂點 i 和 j 之間的最短路距離。 FOR all edge e(i,j) in E DO d(i,j) = we。 END 可以頂點 1,2,…,k 為中間點的 i和j之間的最短路只有兩種可能： 沒有經過頂點 k： dk+1(i,j) = dk(i,j) 經過頂點 k： dk+1(i,j) = dk(i,k) + dk(k,j) 2023年春季 通信網(wǎng)絡理論基礎 69 / 70 小結（ part 05） LabelCorrecting AllPair LabelSetting 最短路算法 基本 Dijkstra ? 問題描述 ? 求解思路 ? 偽碼及示例 ? 代碼設計 算法分析 ? 正確性 ? 復雜度 功能擴展 ? 單源單宿 ? 最大通過率 ? 帶寬約束 ? 分離路徑對 性能加速 ? Dial實現(xiàn) ? 雙向 Dijkstra ? A* 應用 鏈路狀態(tài)路由協(xié)議 負權重問題 應用 距離矢量路由協(xié)議 BellmanFord ? 最優(yōu)性條件 ? 一般的 LabelCorrecting ? FIFO實現(xiàn) ? ModifiedLabelCorrecting 重復最短路 FloydWarshall ? 最優(yōu)性條件 ? AllPair LabelCorrecting 共計 4個 Project： 21 ~ 23， R1 2023年春季 通信網(wǎng)絡理論基礎 Trees and Flow, Rock Roll ! 演講完畢，謝謝觀看！ 。 FOR k = 1 to n DO FOR every vertex i and j in V DO IF d(i,j) d(i,k) + d(k,j) THEN d(i,j) = d(i,k) + d(k,j) 。 p(i,j) = NULL。 顯然 dn+1(i,j)一定是最短路。 2023年春季 通信網(wǎng)絡理論基礎 67 / 70 FloydWarshall算法 (1/2) 怎么可能？ 哪怕只是檢查一組 d(i,j)是否滿足最優(yōu)性條件，就需要 O(n3)，更不要說還要更新（多次檢查）了！ 1） FloydWarshall算法是 AllPair LabelCorrecting 的 一種特殊的實現(xiàn)。 針對每個節(jié)點對，每輪需要進行 n次三角操作。 FOR all edge e(i,j) in E DO d(i,j) = we。 a s b d(b) d(a) w 2023年春季 通信網(wǎng)絡理論基礎 65 / 70 AllPair LabelCorrecting 最優(yōu)性條件 令 d(i,j)表示從頂點 i 到頂點 j 的距離標記。 存在負權重怎么辦？ 調用 n遍 BellmanFord唄，還能怎么辦？ 2023年春季 通信網(wǎng)絡理論基礎 重復最短路：怎么可能？ 64 / 70 算法設計 1遍 BellmanFord加上 (n – 1)遍 Dijkstra ? 第一次 BellmanFord后，如果存在負圈 ，則整個 問題無解。那么，針對 AllPair最短路問題，是否存在更簡單的算法？ 3 AllPair最短路算法 2023年春季 通信網(wǎng)絡理論基礎 63 / 70 重復最短路：思路 基本思路 調用單源最短路算法n次。 ? 分布式計算。 ? 除非存在負圈。 若 j?LIST就插入 LIST； END WHILE ? 一次循環(huán)中，不必檢查所有的邊。 p(s) = NULL。 第四、五和六輪呢？ 浪費。問k+1次循環(huán)后，還是這樣么？ YES， IT IS. u s v k跳 k+1跳 k輪后 ，已知 d(u)=d*(u) k+1輪檢查 e(u,v)時 d(v) ? d*(u)+we? d(v) d*(u)+we? k+1輪結束后，必有 d(v) = d*(u)+we = d*(v) 這不可能，因為與假設 矛盾。 顯然， BellmanFord算法的復雜度為 O(nm)。 2）假如 s到 j實際上的最短路有 k跳，那么 k輪循環(huán)后， d(j)必然會被更新為 d*(j)。 ? 每次循環(huán)都遍歷所有的 m條邊，發(fā)現(xiàn)某條邊不滿足最優(yōu)性條件，就更新。 復雜度： O(n2C) 怎么檢測負圈？ 如果某個距離標記小于等于 ?nC時，必然存在負圈 。 p(s) = NULL。 證明： 任取一條 P(s?j)；該路徑上的每條邊都可以寫出上述不等式；求和可知： d(j)是所有P(s?j)的距離下限。所有頂點的距離標記就是最短路距離值的充要條件是 ：對 所有的邊 e(i,j)，都有 d(j) ? d(i) + we(i,j) 必要性： 如果所有距離標記等于最短路的距離，那么它們必然滿足上述條件。 2023年春季 通信網(wǎng)絡理論基礎 52 / 70 LabelCorrecting算法 負權重 1 2 3 4 一般的 LabelCorrecting BellmanFord算法 應用 2023年春季 通信網(wǎng)絡理論基礎 基本思想 53 / 70 基本思路 ? 找到最短路的某些特征。如果存在最短路，就求出來，如果存在負圈，就檢測出來。 2023年春季 通信網(wǎng)絡理論基礎 負圈 51 / 70 a s c b 5 1 2 ?6 d 1 更糟的情況：不僅有負權重，而且存在負圈。如果存在負權重，這個邏輯不再成立。 鏈路發(fā)生失效后， E知道，而 D不知道。 難道鏈路狀態(tài)協(xié)議在任何情況下都能保證這種一致性？ A以為到 F的最短路 E以為到 F的最短路 會出現(xiàn)這種情況么？ 不一定。 如果存在多條最短路，不就會產生不一致么？ 這不是不一致，因為兩條路徑權重一樣。 最終所有路由器都獲得了全局拓撲信息。 2023年春季 通信網(wǎng)絡理論基礎 43 / 70 LabelSetting算法 4 基本 Dijkstra算法 1 2 3 5 分析 (Analysis) 擴展 (Extension) 加速 (Speed up) 應用 (Application) 2023年春季 通信網(wǎng)絡理論基礎 44 / 70 應用：鏈路狀態(tài)路由協(xié)議 OSPF(Open Shortest Path First)協(xié)議是 IP網(wǎng)絡中鏈路狀態(tài)協(xié)議的代表。 目的 不是把 d(j)的大小作為 FindMin的依據(jù)，而是把d(j)+h(j)作為依據(jù)。 B）對比 /定量研究 Dijkstra算法和雙向 Dijkstra算法的性