【正文】 遞推 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) = ?。 FOR all vertex i in V DO d(i,i) = 0。 只要 i 的鄰接點(diǎn)不斷地告訴 i 它們到其它目的點(diǎn)的距離發(fā)生了怎樣的變化， i 就可以據(jù)此計(jì)算它到網(wǎng)絡(luò)中其它點(diǎn)怎么走最短。 2第三輪呢？ 所有頂點(diǎn)都沒有更新。 況且： 就沒有復(fù)雜度更低的實(shí)現(xiàn)方法了么？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 56 / 70 LabelCorrecting算法 負(fù)權(quán)重 1 2 3 4 一般的 LabelCorrecting BellmanFord算法 應(yīng)用 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 57 / 70 FIFO實(shí)現(xiàn) (BellmanFord) 算法描述 ? 算法由 n次循環(huán)構(gòu)成。所有頂點(diǎn)的距離標(biāo)記就是最短路距離值的充要條件是： 對所有的邊 e(i,j)，都有 d(j) ? d(i) + we(i,j) 算法設(shè)計(jì) 檢查圖中邊 e(i, j)，若它不滿足最優(yōu)性條件，就更新其距離標(biāo)記： d(j) = d(i) + we(i,j) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最優(yōu)性條件 54 / 70 最優(yōu)性條件 令 d(j)表示源點(diǎn) s到頂點(diǎn) j的距離標(biāo)記。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 48 / 70 最短路算法 1 2 LabelSetting算法 LabelCorrecting算法 Dijkstra算法只適用于正權(quán)重圖，針對具有負(fù)權(quán)重（甚至負(fù)圈）的圖，該怎么辦？ 3 AllPair最短路算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 49 / 70 LabelCorrecting算法 負(fù)權(quán)重 1 2 3 4 一般的 LabelCorrecting BellmanFord算法 應(yīng)用 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 50 / 70 負(fù)權(quán)重 Dijkstra算法為什么只能用于非負(fù)權(quán)重的圖？ 之所以 FindMin得到的頂點(diǎn)可以被永久標(biāo)記，因?yàn)樵擁旤c(diǎn)的距離不可能被改進(jìn)了。 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)信息的洪泛 拓?fù)鋱D的構(gòu)造 X A B C D 鏈路狀態(tài)更新是定時的，或檢測到變化。 對這個 listCPath*排序，然后輸出第一個元素。 目的 交替地從 V – SF 和 V – SB 中選擇頂點(diǎn)進(jìn)行永久標(biāo)記，直至 SF和 SB存在相同點(diǎn) w時停止。 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ǔ) 實(shí)現(xiàn)細(xì)節(jié)提示 (1/2) 33 / 70 Dial算法實(shí)現(xiàn)難點(diǎn) 難點(diǎn) 1：基于桶的 FindMin 難點(diǎn) 2：桶的更新 //桶的實(shí)現(xiàn)： mapint,mapint, CVertex* mapBuckets。 b s c d 4 4 1 1 1 算法不完備。 怎樣實(shí)現(xiàn)？ 修改 update函數(shù)。 Update(s)。 } } 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 代碼： Update 18 / 70 void CGraph::Update(int v) { listCEdge* lEdge = mapVID_listEdge[v]。 bool pVertexComp ( CVertex* x, CVertex* y ) { if ( xd yd ) return TRUE。 Update(int VID)。 END IF END FOR FindMin () Find vertex v in V – S which has minimum d(v)。 END IF END FOR FindMin () Find vertex v in V – S which has minimum d(v)。 加哪個頂點(diǎn)？ 從所有與樹鄰接的頂點(diǎn)中，選擇離源點(diǎn)最近的。 怎么知道誰最近？ 對每個頂點(diǎn)，都用一個距離標(biāo)記(Label)來記錄。 RETURN v。 RETURN v。 public: CGraph(char* inputFile)。 return FALSE。 listCEdge*::iterator i,iend。 WHILE S ? V DO i = FindMin()。 修改權(quán)重，然后調(diào)用 DijkstraAlg。 b a c d 4 4 1 1 1 e 8 8 不是最佳解。 內(nèi)層的 map的 key是頂點(diǎn) ID。 方法 ?P(s,w)+P(w,d) ?P(s,u)+e(u,v)+P(v,d), for all u?SF, v?SB ?上述路徑中具有最小權(quán)重的路徑作為輸出。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 39 / 70 研究性 Project ? 自己設(shè)計(jì)實(shí)驗(yàn)，并通過大量實(shí)驗(yàn)結(jié)果來得出你的結(jié)論。 最終所有路由器都獲得了全局拓?fù)湫畔ⅰＨ绻嬖谪?fù)權(quán)重，這個邏輯不再成立。所有頂點(diǎn)的距離標(biāo)記就是最短路距離值的充要條件是 ：對 所有的邊 e(i,j)，都有 d(j) ? d(i) + we(i,j) 必要性： 如果所有距離標(biāo)記等于最短路的距離，那么它們必然滿足上述條件。 ? 每次循環(huán)都遍歷所有的 m條邊，發(fā)現(xiàn)某條邊不滿足最優(yōu)性條件，就更新。 第四、五和六輪呢？ 浪費(fèi)。 ? 分布式計(jì)算。 FOR all edge e(i,j) in E DO d(i,j) = we。 p(i,j) = NULL。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) FloydWarshall算法 (2/2) 68 / 70 dk(i,j) 假如只準(zhǔn)經(jīng)過前 k–1 個頂點(diǎn)的話，頂點(diǎn) i 和 j 之間的最短路距離。所有這些距離標(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) = ?。 反過來， i 到某個目的點(diǎn) d 的距離何時更新？ 當(dāng) i 的正向鄰接點(diǎn)到 d 的距離發(fā)生了更新時。 第二輪呢？ 除了 c和 e外，都沒有更新。 但是： 總得有個具體的方法吧。 最優(yōu)性條件 令 d(j)表示源點(diǎn) s到頂點(diǎn) j的距離標(biāo)記。 失效的快速恢復(fù)是前沿課題。 路由器如何實(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！ 對每個包進(jìn)行獨(dú)立的轉(zhuǎn)發(fā)判決 每個包都自己描述自己 源地址 目的地址 內(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)變化，所以采用一個協(xié)議，由每個路由器動態(tài)、分布式地自動獲取 /更新。 若存在 ，就重構(gòu)出一 條路徑 p(從 s到 d)，放入一個 listCPath*中。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 37 / 70 雙向 Dijkstra算法 針對單源單宿最短路問題，同時運(yùn)行正向和反