【正文】 和 c沒(méi)有被更新。 第二輪呢？ 除了 c和 e外，都沒(méi)有更新。 2第三輪呢？ 所有頂點(diǎn)都沒(méi)有更新。 第四、五和六輪呢？ 浪費(fèi)。 Modified_Label_Correcting(G(V, E), s) FOR all vertex j in V DO d(j) = ?。 p(j) = NULL。 d(s) = 0。 p(s) = NULL。 LIST = {s}。 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。 p(j) = i。 若 j?LIST就插入 LIST； END WHILE ? 一次循環(huán)中，不必檢查所有的邊。 ? 上一輪中沒(méi)有更新的頂點(diǎn)所“發(fā)出”的邊都不必檢查。 ? 不需要 n 輪循環(huán)。 ? 只要能檢測(cè)出某一輪中沒(méi)有更新距離標(biāo)記，就可以終止循環(huán)。 ? 除非存在負(fù)圈。 0 LIST = {s} ? ? ? ? ? ? 3 {} {a}6{af} 3e} {fe5 b}4{eb} 6{ebd} {bd}nhcuj7d32{e}9{ec}{c}2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 60 / 70 LabelCorrecting算法 負(fù)權(quán)重 1 2 3 4 一般的 LabelCorrecting BellmanFord算法 應(yīng)用 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 61 / 70 A B C D 2 1 3 7 1 應(yīng)用：距離矢量路由協(xié)議 目的 距離 端口 B 2 B C 7 C D ? 目的 距離 端口 A 2 A C 1 C D 3 D 目的 距離 端口 A 7 A B 1 B D 1 D 頂點(diǎn) i 的距離標(biāo)記什么時(shí)候需要更新？ 當(dāng) i的反向鄰接點(diǎn)發(fā)生了更新時(shí)。 反過(guò)來(lái)， i 到某個(gè)目的點(diǎn) d 的距離何時(shí)更新？ 當(dāng) i 的正向鄰接點(diǎn)到 d 的距離發(fā)生了更新時(shí)。 只要 i 的鄰接點(diǎn)不斷地告訴 i 它們到其它目的點(diǎn)的距離發(fā)生了怎樣的變化， i 就可以據(jù)此計(jì)算它到網(wǎng)絡(luò)中其它點(diǎn)怎么走最短。 ? 分布式計(jì)算。 目的 距離 端口 A ? B 3 B C 1 C 這種分布式迭代計(jì)算是否能保證收斂？ ?LabelCorrecting算法的原理保證了其收斂性。 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) (注意：不是洪泛 )； ? 直至沒(méi)有更新為止。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 62 / 70 最短路算法 1 2 LabelSetting算法 LabelCorrecting算法 Dijkstra算法和 BellmanFord算法解決的是單源最短路問(wèn)題。那么，針對(duì) AllPair最短路問(wèn)題，是否存在更簡(jiǎn)單的算法？ 3 AllPair最短路算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 63 / 70 重復(fù)最短路：思路 基本思路 調(diào)用單源最短路算法n次。每次針對(duì)不同的源點(diǎn)。 復(fù)雜度？ 假如使用的最短路算法復(fù)雜度為 S(n,m,C)，則為 O(nS(n,m,C))。 選哪個(gè)最短路算法好？ 當(dāng)然是 Dijkstra好啰，因?yàn)樗炻铩? 存在負(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è) 問(wèn)題無(wú)解。如果 沒(méi)有負(fù)圈，對(duì)所有邊進(jìn)行如下權(quán)重變換： w’e(i,j) = we(i,j) + d(i) – d(j) 這怎么可能？ 因?yàn)槿绻嬖谪?fù)圈，無(wú)論從哪個(gè)源點(diǎn)出發(fā)進(jìn)行 BellmanFord都能檢測(cè)出來(lái)。 還因?yàn)槔玫玫降木嚯x標(biāo)記，可以將邊的權(quán)重變換為非負(fù)值。 ? 在新圖上，從其它頂點(diǎn)出發(fā)分別調(diào)用 1次 Dijkstra算法。 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)記。共有 n2個(gè)這樣的標(biāo)記。所有這些距離標(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) = ?。 FOR all vertex i in V DO d(i,i) = 0。 FOR all edge e(i,j) in E DO d(i,j) = we。 WHILE 存在 3個(gè)頂點(diǎn) i, j, 和 k 滿(mǎn)足 d(i,j)d(i,k)+d(k,j) DO d(i,j) = d(i,k) + d(k,j) 。 END WHILE 三角操作 測(cè)試該不等式并更新 稱(chēng)為三角操作。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 復(fù)雜度分析 66 / 70 復(fù)雜度？ 假定權(quán)重為整數(shù)，且最大值為 C。 針對(duì)每個(gè)節(jié)點(diǎn)對(duì)，每輪需要進(jìn)行 n次三角操作。 最壞情況下，每輪只變小 1（整數(shù)），故最多C輪。 總共多少節(jié)點(diǎn)對(duì)？ 最多多少輪？ n2。 復(fù)雜度： O(n3C) 若放棄整數(shù)假設(shè)，證明方法不同，但結(jié)論一樣。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 67 / 70 FloydWarshall算法 (1/2) 怎么可能？ 哪怕只是檢查一組 d(i,j)是否滿(mǎn)足最優(yōu)性條件，就需要 O(n3)，更不要說(shuō)還要更新（多次檢查）了！ 1） FloydWarshall算法是 AllPair LabelCorrecting 的 一種特殊的實(shí)現(xiàn)。 2） FloydWarshall算法復(fù)雜度為 O(n3)。 因?yàn)樵撍惴ú捎昧艘环N非常聰明的，基于動(dòng)態(tài)規(guī)劃思想的三角操作方法。 dk(i,j) 假如只準(zhǔn)經(jīng)過(guò)前 k–1 個(gè)頂點(diǎn)的話(huà)，頂點(diǎn) i 和 j 之間的最短路距離。 顯然 dn+1(i,j)一定是最短路。 先對(duì)所有的頂點(diǎn)對(duì) i 和 j 計(jì)算 d1(i,j)，然后是 d2(i,j)；直至最后達(dá)到 dn+1(i,j) 。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) FloydWarshall算法 (2/2) 68 / 70 dk(i,j) 假如只準(zhǔn)經(jīng)過(guò)前 k–1 個(gè)頂點(diǎn)的話(huà)，頂點(diǎn) 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) = NULL。 FOR all vertex i in V DO d(i,i) = 0。 FOR all edge e(i,j) in E DO d(i,j) = we。 p(i,j) = i。 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) = p(k,j)。 END 可以頂點(diǎn) 1,2,…,k 為中間點(diǎn)的 i和j之間的最短路只有兩種可能： 沒(méi)有經(jīng)過(guò)頂點(diǎn) k： dk+1(i,j) = dk(i,j) 經(jīng)過(guò)頂點(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 ? 問(wèn)題描述 ? 求解思路 ? 偽碼及示例 ? 代碼設(shè)計(jì) 算法分析 ? 正確性 ? 復(fù)雜度 功能擴(kuò)展 ? 單源單宿 ? 最大通過(guò)率 ? 帶寬約束 ? 分離路徑對(duì) 性能加速 ? Dial實(shí)現(xiàn) ? 雙向 Dijkstra ? A* 應(yīng)用 鏈路狀態(tài)路由協(xié)議 負(fù)權(quán)重問(wè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 ! 演講完畢，謝謝觀看！