【正文】 黑 )幾次？ 如果放松“連通圖”假設(shè)，如何改進(jìn)代碼？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 10 / 70 Dijkstra算法代碼設(shè)計(jì) d(j)和 p(j) 從偽碼到 代碼 如何實(shí)現(xiàn) d(j)和 p(j) Option 1：單獨(dú)用數(shù)組 /vector來實(shí)現(xiàn) ； Option 2：創(chuàng)建一個(gè) CVertex類來記錄； 思路 ? 兩個(gè)方法都可以； ? 使用類便于 擴(kuò)展和封裝 。 END WHILE Update ( i ) FOR each edge e incident to i DO IF + d(i) d() THEN d() = + d(i)。 Update(s)。 p(j) = NULL。 d(j): 頂點(diǎn) j的距離標(biāo)記。 END WHILE Update ( i ) FOR each edge e incident to i DO IF + d(i) d() d() = + d(i)。 Update(s)。 p(j) = NULL。 距離 標(biāo)記？ 每次循環(huán)都需要對距離標(biāo)記進(jìn)行更新。 3) 存在多條最短路時(shí) ,只求 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)。 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è)計(jì) 算法示例 求解思路 偽碼描述 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)重最小的路徑。 怎樣實(shí)現(xiàn)？ 構(gòu)造一個(gè)循環(huán)，每次循環(huán)都增加一個(gè)頂點(diǎn)到最短路徑樹上。 如何維護(hù)最短路徑樹？ 如何選擇頂點(diǎn)？ 如何更新距離標(biāo)記？ 樹上頂點(diǎn)的集合 S。 S= {s}。 WHILE S ? V DO i = FindMin()。 p() = i。 p(j): 頂點(diǎn) j在最短路徑樹上的前繼點(diǎn)。 S = {s}。 WHILE S ? V DO i = FindMin()。 p() = i。 細(xì)節(jié) ? 構(gòu)造函數(shù)？ ? 接口函數(shù)？ 代碼設(shè)計(jì) 創(chuàng)建一個(gè) CVertex類 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 11 / 70 Dijkstra算法代碼設(shè)計(jì) d(j)和 p(j) 如何管理 從偽碼到 代碼 代碼設(shè)計(jì) 在 CGraph中增加一個(gè) CVertex的 map 創(chuàng)建一個(gè) CVertex類 如何管理這些 CVertex對象？ ? Q 1：用什么數(shù)據(jù)結(jié)構(gòu)？ ? Q 2：這個(gè)數(shù)據(jù)結(jié)構(gòu)放在哪里？ 思路 ? 用一個(gè) map，以 ID為 key； ? 放在 CGraph里面。 細(xì)節(jié) ? 如何更改循環(huán)判決條件？ ? list的 sort需要能對對象實(shí)現(xiàn)比較判決。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 代碼： CGraph類 15 / 70 class CGraph{ private: int numVertex, numEdge。 // 記錄與頂點(diǎn)關(guān)聯(lián)的出度邊 mapint, listCEdge* mapVID_listEdge。 CGraph(CGraph )。 DijkstraAlg(int VID)。 int ID。 }。 如果 sort的是對象本身，可以用重載 來實(shí)現(xiàn)。 for( i=()。 } Update(s)。 Update(j)。 for( i = ()。 CVertex* t = mapVID_Vertex[v]。 復(fù)雜度分析 正確性分析 Dijkstra算法分析 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 21 / 70 正確性分析 k?k+1 問題變化 問題 1： Dijkstra算法求出的是從 s到其他頂點(diǎn)的最短路么？ k=1 第一次循環(huán) (k=1)時(shí)， 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) = ?。 p(s) = NULL。 Update(i)。 怎樣實(shí)現(xiàn)？ 重載一個(gè) 2參數(shù)的 DijkstraAlg函數(shù)。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 26 / 70 最大通過率路徑 最大通過率路徑問題 給定加權(quán)圖 G，邊上權(quán)重表示業(yè)務(wù)流經(jīng)該邊時(shí)的通過比例（大于 0小于 1）。 路徑通過率與邊的通過率是什么關(guān)系？ 乘性關(guān)系。給定源點(diǎn) s，以及帶寬需求 C。 根據(jù) IncidentList求 mapVID_listEdge，然后調(diào)用 DijkstraAlg。給定源點(diǎn) s和宿點(diǎn) d。 Suurballe算法 ? 在 G上求最短路 p； ? p上邊反向，得到新圖 G’； ? 在 G’上求最短路 p’； ? 刪除 p和 p’中重復(fù)的邊； ? 重新組合 p和 p’中的邊。著重講一種理論上有效（且有趣）的加速方法，以及兩種現(xiàn)實(shí)中很有效的方法。 更新 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) = ?。 p(s) = NULL。 Update(i)。 外層的 map的 key是距離標(biāo)記。 遞增該迭代器，直至對應(yīng)的桶的 empty函數(shù)返回 FALSE。著重講一種理論上有效（且有趣）的加速方法，以及兩者現(xiàn)實(shí)中很有效的方法。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 37 / 70 雙向 Dijkstra算法 針對單源單宿最短路問題，同時(shí)運(yùn)行正向和反向Dijkstra算法，以期減少不必要的永久標(biāo)記點(diǎn)。 SF表示正向算法中的永久標(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)體。 循環(huán)體中要同時(shí)進(jìn)行兩個(gè)方向的 FindMin和 Update。 若存在 ，就重構(gòu)出一 條路徑 p(從 s到 d)，放入一個(gè) listCPath*中。包括問題的描述；求解方法的描述；實(shí)驗(yàn)設(shè)計(jì)思路；結(jié)果分析；結(jié)論；改進(jìn)實(shí)驗(yàn)的方向等。著重講一種理論上有效（且有趣）的加速方法，以及兩者現(xiàn)實(shí)中很有效的方法。 實(shí)現(xiàn) h(j)表示頂點(diǎn) j到宿點(diǎn) d的距離下限 h(j)是啟發(fā)式方法得到的，通信網(wǎng)中可用歐氏距離 e(u,v)表示從頂點(diǎn) u到 v的一條有向邊。 路由器如何實(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)、分布式地自動獲取 /更新。這種分布式判決機(jī)制