【正文】 何修改 Dijkstra算法來求解這個(gè)問題？ 增加一個(gè)判斷分支，永久標(biāo)記 d時(shí)，停止循環(huán)。給定頂點(diǎn) s，求從 s出發(fā)到其他頂點(diǎn)的最大通過率路徑。 怎樣實(shí)現(xiàn)？ 需要遍歷所有的邊，即 IncidentList。ve Idea ? 在 G上求最短路 p； ? 刪除 p上邊，得到新圖 G’； ? 在 G’上求最短路 p’； ? 輸出 p和 p’。 性能 每次 Update時(shí)，也需要更新桶。 S = S U {i}。 FindMin中，用于指向具體的桶。 a s c b 5 3 2 4 2 d 2 Dijkstra算法 a s c b 5 3 2 4 2 d 2 反向 Dijkstra算法 ? 這就是所謂反向 Dijkstra算法。 P(x,y)表示從 x到 y的最短路徑。 Hint 3 逐一檢查 SF中的頂點(diǎn)，看他的鄰接點(diǎn)是否在 SB中。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 40 / 70 加速 (Speed up) 本課程略去了利用各種“堆”數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn) Dijkstra算法加速的內(nèi)容。其中采用的就是 Dijkstra算法。 如果兩個(gè)路由器對(duì)拓?fù)涞睦斫獠煌兀? 是的，這樣會(huì)導(dǎo)致不一致。 E以為到 C的最短路是什么？ D以為到 C的最短路是什么？ 在 D獲知狀態(tài)更新之前，目的為 C的分組路由成環(huán)，延遲，丟失。 如果不要求解必須為簡單路徑，那么不存在最短路。 ? 設(shè)計(jì)一個(gè)算法不斷地改進(jìn)解的性能，直到解呈現(xiàn)出這些特征。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 55 / 70 一般的 LabelCorrecting算法 Label_Correcting(G(V, E), s) FOR all vertex j in V DO d(j) = ?。 靈活性： 可以用任意方式 /順序檢查邊，都能保證收斂。 d*(x)表示s到 x的最短路的距離。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 59 / 70 加速 3 s a b f e d c 2 3 3 1 6 2 3 2 4 4 3 ? 0?? ???0+3 ? ? ? 33+2 ? ? ? 536 946第一輪結(jié)束后，頂點(diǎn) s和 c沒有被更新。 LIST = {s}。 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í)。每次針對(duì)不同的源點(diǎn)。共有 n2個(gè)這樣的標(biāo)記。 最壞情況下，每輪只變小 1（整數(shù)），故最多C輪。 先對(duì)所有的頂點(diǎn)對(duì) i 和 j 計(jì)算 d1(i,j)，然后是 d2(i,j)；直至最后達(dá)到 dn+1(i,j) 。 p(i,j) = p(k,j)。 FOR all vertex i in V DO d(i,i) = 0。 2） FloydWarshall算法復(fù)雜度為 O(n3)。 WHILE 存在 3個(gè)頂點(diǎn) i, j, 和 k 滿足 d(i,j)d(i,k)+d(k,j) DO d(i,j) = d(i,k) + d(k,j) 。如果 沒有負(fù)圈，對(duì)所有邊進(jìn)行如下權(quán)重變換： w’e(i,j) = we(i,j) + d(i) – d(j) 這怎么可能？ 因?yàn)槿绻嬖谪?fù)圈，無論從哪個(gè)源點(diǎn)出發(fā)進(jìn)行 BellmanFord都能檢測(cè)出來。 目的 距離 端口 A ? B 3 B C 1 C 這種分布式迭代計(jì)算是否能保證收斂？ ?LabelCorrecting算法的原理保證了其收斂性。 ? 上一輪中沒有更新的頂點(diǎn)所“發(fā)出”的邊都不必檢查。 Modified_Label_Correcting(G(V, E), s) FOR all vertex j in V DO d(j) = ?。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 58 / 70 FIFO實(shí)現(xiàn) (BellmanFord) 2）假如 s到 j實(shí)際上的最短路有 k跳，那么 k輪循環(huán)后， d(j)必然會(huì)被更新為 d*(j)。 ? 如果第 n次循環(huán)還有更新，說明有負(fù)圈。 WHILE some e(i,j) satisfies d(j)d(i)+we DO d(j) = d(i) + we。 證明： 如果 d(j)大于 d(i)+we，那么至少存在一條路徑 s?i?j的距離小于 d(j)。 LabelCorrecting算法就能達(dá)到這個(gè)目的。 a s c b 6 2 2 ?4 負(fù)權(quán)重有什么用？ 雖然通信網(wǎng)絡(luò)中很少會(huì)出現(xiàn)負(fù)權(quán)重，但在其他問題中有可能。因?yàn)殒溌窢顟B(tài)的更新是需要時(shí)間的。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 47 / 70 分布式判決的一致性 A B C D E F 5 2 1 2 3 3 1 3 2 1 路由器只能控制路徑的下一跳，后面的路由器獨(dú)立做出轉(zhuǎn)發(fā)判決。 方法 ? 以歐氏距離作 h(j)，并更改所有邊的權(quán)重： e(u,v).weight = e(u,v).weight + h(v) – h(u) ? 在新圖上調(diào)用 Dijkstra算法。 ? 提交 研究報(bào)告 。 Hint 1 循環(huán)的終止條件為某個(gè)頂點(diǎn)被兩個(gè)方向都永久標(biāo)記。 比較 只要不是給定的宿點(diǎn)，都不必要。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 35 / 70 加速 (Speed up) 本課程略去了利用各種“堆”數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn) Dijkstra算法加速的內(nèi)容。該 map代表單個(gè)的桶。 d(s) = 0。 b a c d 4 4 1 1 1 b a c d 4 4 1 1 1 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 29 / 70 LabelSetting算法 4 基本 Dijkstra算法 1 2 3 5 分析 (Analysis) 擴(kuò)展 (Extension) 加速 (Speed up) 應(yīng)用 (Application) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 30 / 70 加速 (Speed up) 本課程略去了利用各種“堆”數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn) Dijkstra算法加速的內(nèi)容。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 28 / 70 最短分離路徑對(duì) (Shortest Disjoint Path Pair) 最短分離路徑對(duì)問題 給定加權(quán)圖 G。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 27 / 70 帶寬約束下的最短路 帶寬約束下的最短路問題 給定加權(quán)圖 G，每條邊上既有權(quán)重，也有 capacity。要求設(shè)計(jì)一個(gè) CPath類，從Dijkstra計(jì)算得到的 CVertex中重構(gòu)出一個(gè) CPath對(duì)象，并輸出。 S = S U {i}。 } } } 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 19 / 70 LabelSetting算法 4 基本 Dijkstra算法 1 2 3 5 分析 (Analysis) 擴(kuò)展 (Extension) 加速 (Speed up) 應(yīng)用 (Application) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 20 / 70 分析 (Analysis) 正確性分析和復(fù)雜度分析是算法分析中兩個(gè)主要的內(nèi)容。 iend = ()。 (isecond)。 }。 int p。 CGraph(listCEdge* listEdge)。 細(xì)節(jié) ? CGraph里存儲(chǔ)這個(gè)數(shù)據(jù)結(jié)構(gòu)？ ? 頂點(diǎn) ?邊 ?頂點(diǎn)的操作細(xì)節(jié)。 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 ? ? 每條邊被檢查了 (被描黑 )幾次？ 如果放松“連通圖”假設(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ò)展和封裝 。