【正文】 Update(s)。 d(j): 頂點(diǎn) j的距離標(biāo)記。 Update(s)。 距離 標(biāo)記？ 每次循環(huán)都需要對距離標(biāo)記進(jìn)行更新。 3 AllPair最短路算法 3 / 70 LabelSetting算法 4 基本 Dijkstra算法 1 2 3 5 分析 (Analysis) 擴(kuò)展 (Extension) 加速 (Speed up) 應(yīng)用 (Application) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 4 / 70 基本 Dijkstra算法 Dijkstra算法是本課程的核心內(nèi)容 ， 務(wù)必 要掌握其思想和具體的編程方法。 怎樣實(shí)現(xiàn)？ 構(gòu)造一個(gè)循環(huán)，每次循環(huán)都增加一個(gè)頂點(diǎn)到最短路徑樹上。 S= {s}。 p() = i。 S = {s}。 p() = i。 細(xì)節(jié) ? 如何更改循環(huán)判決條件？ ? list的 sort需要能對對象實(shí)現(xiàn)比較判決。 // 記錄與頂點(diǎn)關(guān)聯(lián)的出度邊 mapint, listCEdge* mapVID_listEdge。 DijkstraAlg(int VID)。 }。 for( i=()。 Update(j)。 CVertex* t = mapVID_Vertex[v]。 p(s) = NULL。 怎樣實(shí)現(xiàn)？ 重載一個(gè) 2參數(shù)的 DijkstraAlg函數(shù)。 路徑通過率與邊的通過率是什么關(guān)系？ 乘性關(guān)系。 根據(jù) IncidentList求 mapVID_listEdge，然后調(diào)用 DijkstraAlg。 Suurballe算法 ? 在 G上求最短路 p； ? p上邊反向，得到新圖 G’； ? 在 G’上求最短路 p’； ? 刪除 p和 p’中重復(fù)的邊； ? 重新組合 p和 p’中的邊。 更新 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 32 / 70 Dijkstra算法的 Dial實(shí)現(xiàn) ? s a e d b c 2 4 1 4 2 3 3 2 2 ? ? ? ? ? 0 2,s 4,s DijkstraAlg (G(V, E), s) FOR all vertex j in V DO d(j) = ?。 Update(i)。 遞增該迭代器，直至對應(yīng)的桶的 empty函數(shù)返回 FALSE。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 37 / 70 雙向 Dijkstra算法 針對單源單宿最短路問題，同時(shí)運(yùn)行正向和反向Dijkstra算法，以期減少不必要的永久標(biāo)記點(diǎn)。 為什么要進(jìn)行這樣的比較？ 說明： a s c b 5 3 2 4 2 d 2 交集為 c，但 sacd的距離大于sabd 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 38 / 70 實(shí)現(xiàn)細(xì)節(jié)提示 雙向 Dijkstra實(shí)現(xiàn)難點(diǎn) 難點(diǎn) 1：要改變循環(huán)體。 若存在 ，就重構(gòu)出一 條路徑 p(從 s到 d)，放入一個(gè) listCPath*中。著重講一種理論上有效（且有趣）的加速方法，以及兩者現(xiàn)實(shí)中很有效的方法。 路由器如何實(shí)現(xiàn)轉(zhuǎn)發(fā)？ 什么情況下不一致？ 分布式判決能否一致？ 轉(zhuǎn)發(fā)表是怎么來的？ 怎樣應(yīng)用 Dijkstra算法？ OSPF協(xié)議 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 45 / 70 轉(zhuǎn)發(fā)表 目的 端口 表項(xiàng) 1 A 2 表項(xiàng) 2 B 2 表項(xiàng) 3 C 3 表項(xiàng) n … … 目的地址 B 目的地址 A 目的地址 C 端口 2 端口 1 端口 3 R 路由器 R的轉(zhuǎn)發(fā)表 IP路由原理 C A Hi！ 對每個(gè)包進(jìn)行獨(dú)立的轉(zhuǎn)發(fā)判決 每個(gè)包都自己描述自己 源地址 目的地址 內(nèi)容 怎么可能 如何描述 如何轉(zhuǎn)發(fā) 目的地址 +轉(zhuǎn)發(fā)表 什么是轉(zhuǎn)發(fā)表 轉(zhuǎn)發(fā)表是怎么得到的？ R憑什么決定去往目的地 A應(yīng)該走端口 2， 而不是端口 1？ 因?yàn)槎丝?2對應(yīng)的鏈路在從 R到 A的最短路上 怎么算的最短路？ Dijkstra算法 圖的數(shù)據(jù)哪里來？ 靜態(tài)配置無法適應(yīng)動態(tài)變化，所以采用一個(gè)協(xié)議，由每個(gè)路由器動態(tài)、分布式地自動獲取 /更新。 D知道該變化，但 A不知道。 失效的快速恢復(fù)是前沿課題。 如果要求解必須為簡單路徑，那么該問題是 NP完全問題，與最長路問題一樣難。 最優(yōu)性條件 令 d(j)表示源點(diǎn) s到頂點(diǎn) j的距離標(biāo)記。 p(j) = NULL。 但是： 總得有個(gè)具體的方法吧。 上述事實(shí)意味著，該算法最多經(jīng)過 n?1輪循環(huán)就可以保證所有的距離標(biāo)記都更新為最佳值。 第二輪呢？ 除了 c和 e外，都沒有更新。 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。 反過來， i 到某個(gè)目的點(diǎn) d 的距離何時(shí)更新？ 當(dāng) i 的正向鄰接點(diǎn)到 d 的距離發(fā)生了更新時(shí)。 復(fù)雜度？ 假如使用的最短路算法復(fù)雜度為 S(n,m,C)，則為 O(nS(n,m,C))。所有這些距離標(biāo)記就是最短路距離值的 充要條件是： 對所有的 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) = ?。 總共多少節(jié)點(diǎn)對？ 最多多少輪？ n2。 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 之間的最短路距離。 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ò)展 ? 單源單宿 ? 最大通過率 ? 帶寬約束 ? 分離路徑對 性能加速 ? 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 ! 演講完畢，謝謝觀看！ 。 p(i,j) = NULL。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 67 / 70 FloydWarshall算法 (1/2) 怎么可能？ 哪怕只是檢查一組 d(i,j)是否滿足最優(yōu)性條件，就需要 O(n3)，更不要說還要更新（多次檢查）了！ 1） FloydWarshall算法是 AllPair LabelCorrecting 的 一種特殊的實(shí)現(xiàn)。 FOR all edge e(i,j) in E DO d(i,j) = we。 存在負(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è) 問題無解。 ? 分布式計(jì)算。 若 j?LIST就插入 LIST； END WHILE ? 一次循環(huán)中，不必檢查所有的邊。 第四、五和六輪呢？ 浪費(fèi)。 顯然， BellmanFord算法的復(fù)雜度為 O(nm)。 ? 每次循環(huán)都遍歷所有的 m條邊，發(fā)現(xiàn)某條邊不滿足最優(yōu)性條件，就更新。 p(s) = NULL。所有頂點(diǎn)的距離標(biāo)記就是最短路距離值的充要條件是 ：對 所有的邊 e(i,j)，都有 d(j) ? d(i) + we(i,j) 必要性： 如果所有距離標(biāo)記等于最短路的距離，那么它們必然滿足上述條件。如果存在最短路，就求出來，如果存在負(fù)圈，就檢測出來。如果存在負(fù)權(quán)重，這個(gè)邏輯不再成立。 難道鏈路狀態(tài)協(xié)議在任何情況下都能保證這種一致性？ A以為到 F的最短路 E以為到 F的最短路 會出現(xiàn)這種情況么？ 不一定。 最終所有路由器都獲得了全局拓?fù)湫畔ⅰ? 目的 不是把 d(j)的大小作為 FindMin的依據(jù)，而是把d(j)+h(j)作為依據(jù)。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 39 / 70 研究性 Project ? 自己設(shè)計(jì)實(shí)驗(yàn)，并通過大量實(shí)驗(yàn)結(jié)果來得出你的結(jié)論。 難點(diǎn) 2：要增加數(shù)據(jù)結(jié)構(gòu)。 方法 ?P(s,w)+P(w,d