【正文】 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é)議的代表。 如果存在多條最短路，不就會產(chǎn)生不一致么？ 這不是不一致，因為兩條路徑權(quán)重一樣。 鏈路發(fā)生失效后， E知道，而 D不知道。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 負(fù)圈 51 / 70 a s c b 5 1 2 ?6 d 1 更糟的情況：不僅有負(fù)權(quán)重，而且存在負(fù)圈。 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 基本思路 ? 找到最短路的某些特征。 證明： 任取一條 P(s?j)；該路徑上的每條邊都可以寫出上述不等式；求和可知： d(j)是所有P(s?j)的距離下限。 復(fù)雜度： O(n2C) 怎么檢測負(fù)圈？ 如果某個距離標(biāo)記小于等于 ?nC時，必然存在負(fù)圈 。 2）假如 s到 j實(shí)際上的最短路有 k跳，那么 k輪循環(huán)后， d(j)必然會被更新為 d*(j)。問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輪結(jié)束后，必有 d(v) = d*(u)+we = d*(v) 這不可能，因為與假設(shè) 矛盾。 p(s) = NULL。 ? 除非存在負(fù)圈。那么，針對 AllPair最短路問題，是否存在更簡單的算法？ 3 AllPair最短路算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 63 / 70 重復(fù)最短路：思路 基本思路 調(diào)用單源最短路算法n次。 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)記。 針對每個節(jié)點(diǎn)對，每輪需要進(jìn)行 n次三角操作。 顯然 dn+1(i,j)一定是最短路。 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) 。 FOR all edge e(i,j) in E DO d(i,j) = we。 因為該算法采用了一種非常聰明的，基于動態(tài)規(guī)劃思想的三角操作方法。 END WHILE 三角操作 測試該不等式并更新 稱為三角操作。 還因為利用得到的距離標(biāo)記，可以將邊的權(quán)重變換為非負(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輪； ? 每當(dāng)路由器發(fā)生了更新，他就將其新的距離矢量發(fā)給他的鄰接點(diǎn) (注意：不是洪泛 )； ? 直至沒有更新為止。 ? 不需要 n 輪循環(huán)。 p(j) = NULL。 d*(x)表示 s到 x的最短路的距離。 為什么 n次循環(huán)就夠了？為什么第 n次有更新就說明存在負(fù)圈？ 1） s到任一其他頂點(diǎn)的最短路徑最多 n?1跳（即經(jīng)過 n?1條邊）。 p(j) = i。矛盾。 BellmanFord算法是 LabelCorrecting算法的一個特例。《 Algorithms in Java》 3rd ed。更新完成以前就可能出現(xiàn)不一致。這種分布式判決機(jī)制是否存在不一致性？ 3?1 1?9 3?9 不會的。 實(shí)現(xiàn) h(j)表示頂點(diǎn) j到宿點(diǎn) d的距離下限 h(j)是啟發(fā)式方法得到的，通信網(wǎng)中可用歐氏距離 e(u,v)表示從頂點(diǎn) u到 v的一條有向邊。包括問題的描述；求解方法的描述；實(shí)驗設(shè)計思路；結(jié)果分析；結(jié)論；改進(jìn)實(shí)驗的方向等。 循環(huán)體中要同時進(jìn)行兩個方向的 FindMin和 Update。 SF表示正向算法中的永久標(biāo)記頂點(diǎn)集合。著重講一種理論上有效（且有趣）的加速方法，以及兩者現(xiàn)實(shí)中很有效的方法。 外層的 map的 key是距離標(biāo)記。 p(s) = NULL。著重講一種理論上有效（且有趣）的加速方法，以及兩種現(xiàn)實(shí)中很有效的方法。給定源點(diǎn) s和宿點(diǎn) d。給定源點(diǎn) s，以及帶寬需求 C。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 26 / 70 最大通過率路徑 最大通過率路徑問題 給定加權(quán)圖 G，邊上權(quán)重表示業(yè)務(wù)流經(jīng)該邊時的通過比例（大于 0小于 1）。 Update(i)。 復(fù)雜度分析 正確性分析 Dijkstra算法分析 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 21 / 70 正確性分析 k?k+1 問題變化 問題 1： Dijkstra算法求出的是從 s到其他頂點(diǎn)的最短路么？ k=1 第一次循環(huán) (k=1)時， Dijkstra算法求出的路徑是什么？它是從 s出發(fā)的最短路么？ 假定第 k次循環(huán)求得了第 k條最短路，問第 k+1次循環(huán)求得的是第 k+1短的路徑么？ 問題 2： Dijkstra算法求出的是從 s出發(fā)的前 n條最短路 (宿點(diǎn)必須不同 )么？ YES， OF COURSE YES， IT IS. s S集合 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 22 / 70 復(fù)雜度分析 DijkstraAlg (G(V, E), s) FOR all vertex j in V DO d(j) = ?。 for( i = ()。 } Update(s)。 如果 sort的是對象本身，可以用重載 來實(shí)現(xiàn)。 int ID。 CGraph(CGraph )。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 代碼： CGraph類 15 / 70 class CGraph{ private: int numVertex, numEdge。 細(xì)節(jié) ? 構(gòu)造函數(shù)？ ? 接口函數(shù)？ 代碼設(shè)計 創(chuàng)建一個 CVertex類 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 11 / 70 Dijkstra算法代碼設(shè)計 d(j)和 p(j) 如何管理 從偽碼到 代碼 代碼設(shè)計 在 CGraph中增加一個 CVertex的 map 創(chuàng)建一個 CVertex類 如何管理這些 CVertex對象？ ? Q 1：用什么數(shù)據(jù)結(jié)構(gòu)？ ? Q 2：這個數(shù)據(jù)結(jié)構(gòu)放在哪里？ 思路 ? 用一個 map，以 ID為 key； ? 放在 CGraph里面。 WHILE S ? V DO i = FindMin()。 p(j): 頂點(diǎn) j在最短路徑樹上的前繼點(diǎn)。 WHILE S ? V DO i = FindMin()。 如何維護(hù)最短路徑樹？ 如何選擇頂點(diǎn)？ 如何更新距離標(biāo)記？ 樹上頂點(diǎn)的集合 S。 問題分析 代碼設(shè)計 算法示例 求解思路 偽碼描述 Dijkstra算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 問題描述 5 / 70 單源最短路問題 給定有向加權(quán)圖 G(V, E)，給定源點(diǎn) /起始點(diǎn) s，求從 s出發(fā)到 V中其它所有頂點(diǎn)的權(quán)重最小的路徑。 3) 存在多條最短路時 ,只求 1條 . 為什么一定是樹？ 最短路上的子路徑也是最短路 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 最短路徑樹 6 / 70 最短路徑樹是生成樹么？ 是的 最短路徑樹是最小生成樹么？ 不一定 A S B C 1 1 2 2 1 A S B C 1 2 2 A S B C 1 2 1 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 7 / 70 Dijkstra的求解思路 算法思路 逐步地發(fā)展最短路徑樹，直至它覆蓋所有頂點(diǎn)。 p(j) = NULL。 END WHILE Update ( i ) FOR each edge e incident to i DO IF + d(i) d() d() = + d(i)。 p(j) = NULL。 END WHILE Update ( i ) FOR each edge e incident to i DO IF + d(i) d() THEN d() = + d(i)。 思路 ? 用一個 list來實(shí)現(xiàn)暫時標(biāo)記頂點(diǎn)集合； ? 用 sort來實(shí)現(xiàn)對 list的排序。 // 暫時標(biāo)記的頂點(diǎn)集合 listCVertex* listTempMark。 int getNumEdge()。} ~CVertex()。 iend = ()。 ()。 CVertex* h = mapVID_Vertex[(*i)getHead()]。 d(s) = 0。 如