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