【正文】 p(i,j) = i。 dk(i,j) 假如只準經(jīng)過前 k–1 個頂點的話，頂點 i 和 j 之間的最短路距離。 2023年春季 通信網(wǎng)絡理論基礎 復雜度分析 66 / 70 復雜度？ 假定權重為整數(shù)，且最大值為 C。 ? 在新圖上，從其它頂點出發(fā)分別調用 1次 Dijkstra算法。 2023年春季 通信網(wǎng)絡理論基礎 62 / 70 最短路算法 1 2 LabelSetting算法 LabelCorrecting算法 Dijkstra算法和 BellmanFord算法解決的是單源最短路問題。 ? 只要能檢測出某一輪中沒有更新距離標記，就可以終止循環(huán)。 d(s) = 0。 k=1 第一次循環(huán)(k=1)后，具有最短路跳數(shù)為 1的那些頂點的距離標記會被更新為最佳值么？ YES， OF COURSE k?k+1 假定第 k次循環(huán)后，所有具有最短路跳數(shù)小于等于 k的那些頂點標記都被更新為最佳值了。除非存在負圈。 END WHILE 分析 負圈 實現(xiàn) 正確性： 該算法 可在 有限步驟內收斂到最佳解。 充分性： 如果所有距離標記都滿足上述條件，那么它們就是最短路的距離。 工程中，一般用 Dijkstra算法（因為它快）；當出現(xiàn)負權重時，用BellmanFord算法。 最典型的例子就是鏈路失效。因為最短路的子路徑必然也是最短路。 說明： 2023年春季 通信網(wǎng)絡理論基礎 A*算法 (2/2) 42 / 70 為什么 A*等效于更改權重后的 Dijkstra？ a s b h(b) w1 d w2 h(s) h(a) w1’=w1+h(a) – h(s) w2’=w2+h(b) – h(a) d’(b)=w1’+w2’ =w1+w2+h(b) – h(s) =d(b)+h(b) – h(s) 與 A*要求的距離標記只差一 個常量 ( – h(s) )。 研究性 Project的要求 研究性 Project No. R1 下面兩項任選一項： A）對比 /定量研究 Dijkstra算法和 Dial算法的性能。 Hint 2 CVertex中要記錄兩個方向 的 距離 和前繼。 e(u,v)表示從頂點 u到 v的一條有向邊。 Dial實現(xiàn) A*算法 雙向 Dijkstra算法 Dijkstra算法加速 2023年春季 通信網(wǎng)絡理論基礎 36 / 70 反向 Dijkstra算法 反向最短路問題 給定宿點 d，求從其他頂點出發(fā)到 d的最短路徑。該 map代表所有的桶。 Update(s)。 Dial實現(xiàn) A*算法 雙向 Dijkstra算法 Dijkstra算法加速 2023年春季 通信網(wǎng)絡理論基礎 31 / 70 Dial實現(xiàn) 通過降低 FindMin的復雜度來加速 目的 Bucket(k) = { i ? i ? V, d(i) = k } 方法 令 C表示最大的權重，則距離標記最大為 nC。求從 s出發(fā)到 d的一對路徑（兩條），要求這兩條路徑“鏈路分離”，且路徑權重之和最小。求從 s出發(fā)到其他頂點的帶寬大于 C的最小權重路徑。給定源點 s，求從 s出發(fā)到其他頂點的最大通過率路徑。 END WHILE 有幾個循環(huán)？ 2 FOR循環(huán)的操作次數(shù)？ 2n WHILE循環(huán)了幾次？ n WHILE循環(huán)的操作次數(shù)呢？ FindMin ? 從 n個數(shù)中求最小，復雜度為 n； ? n+(n1)+…+1 ?n(n1)/2 Update ? 每次循環(huán)檢查的邊的數(shù)目都不同； ? 但是都不重復； ? 總共檢查了 m次 總的操作次數(shù)為： 2n + n(n1)/2 + n + m 結論 ： Dijkstra算法 的 復雜度為 O(n2) 2023年春季 通信網(wǎng)絡理論基礎 23 / 70 LabelSetting算法 4 基本 Dijkstra算法 1 2 3 5 分析 (Analysis) 擴展 (Extension) 加速 (Speed up) 應用 (Application) 2023年春季 通信網(wǎng)絡理論基礎 24 / 70 擴展 (Extension) 針對不同問題的物理意義，通過擴展 Dijkstra算法來達到求解目的。 p(j) = NULL。 i!=iend。 while( ! () ) { (pVertexComp)。這里 sort的是對象指針，所以寫了個外部函數(shù)。 CVertex(){d = INFINITY。 ~CGraph()。 listCEdge* IncidentList。 細節(jié) ? 如何初始化？ ? 什么時候需要查詢 /訪問？ 2023年春季 通信網(wǎng)絡理論基礎 12 / 70 Dijkstra算法代碼設計 DijkstraAlg d(j)和 p(j) 如何管理 從偽碼到 代碼 代碼設計 在 CGraph中增加一個 CVertex的 map 創(chuàng)建一個 CVertex類 在 CGraph中增加一個 DijkstraAlg函數(shù) DijkstraAlg函數(shù)放在哪里？ ? option 1：作為一個獨立的函數(shù) ? option 2：作為 CGraph的成員函數(shù) 思路 ? 兩種都可以，但前者需要傳入圖對象； ? 為了方便 ，放 在 CGraph里。 S = S U {i}。 S: 最短路徑樹上的頂點集合。 S = S U {i}。 頂點的前繼 p(i)。 所有這些最短路構成的是一個 怎樣的子圖 ？ 樹 ?最短路徑樹 假設 1) 權重為正整數(shù) 。 2) 連通圖 。 FindMin() Update(i) 2023年春季 通信網(wǎng)絡理論基礎 8 / 70 偽碼描述 DijkstraAlg (G(V, E), s) FOR all vertex j in V DO d(j) = ?。 Update(i)。 2023年春季 通信網(wǎng)絡理論基礎 9 / 70 怎樣根據(jù)得到的這些信息重構出最短路徑？ Dijkstra算法示例 ? 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)。 細節(jié) ? 使用了哪些 CGraph里的成員變量？ ? 如何設計輸出？ 2023年春季 通信網(wǎng)絡理論基礎 13 / 70 Dijkstra算法代碼設計 DijkstraAlg d(j)和 p(j) 如何管理 FindMin 從偽碼到 代碼 代碼設計 在 CGraph中增加一個 CVertex的 map 創(chuàng)建一個 CVertex類 在 CGraph中增加一個 DijkstraAlg函數(shù) 用一個 list來實現(xiàn)暫時標記的頂點集合 如何實現(xiàn) FindMin？ 物理意義：從暫時標記頂點集合（ V – S）中找出距離標記最小的頂點。 // 所有的頂點 mapint, CVertex* mapVID_Vertex。 int getNumVertex()。 p = NULL。 2023年春季 通信網(wǎng)絡理論基礎 代碼： DijkstraAlg 17 / 70 void CGraph::DijkstraAlg(int s) { mapint, CVertex*::iterator i,iend。 int j = (*())ID。 i++) { int w = (*i)getWeight()。 S = {s}。 單源單宿最短路問題 最短分離路徑對問題 帶寬約束最短路問題 最大通過率路徑問題 Dijkstra算法擴展 2023年春季 通信網(wǎng)絡理論基礎 25 / 70 單源單宿最短路 單源單宿最短路問題 給定加權圖 G，并給定頂點 s和 d，求從 s到 d的最小權重路徑。 Project 給定加權圖 G，邊上權重代表通過率。 求解思路？ 先刪除 capacity小于 C的邊，然后 在新圖 上調用 DijkstraAlg。 Na239。換句話說，最多 nC個桶，F(xiàn)indMin復雜度為 O(nC)。 WHILE S ? V DO i = FindMin()。 Hint 1 2023年春季 通信網(wǎng)絡理論基礎 34 / 70 實現(xiàn)細節(jié) 提示 (2/2) //指向桶的迭代器 mapint,mapint, CVertex* ::iterator itBucket。 ? 注意， CGraph中的 mapVID_listEdge只記錄了出度邊； ? 另外構造一 個數(shù)據(jù)結構 ，記錄每個頂點的入度 邊 :mapVID_listRevEdge； ? 在進行 Update時不按 mapVID_listEdge來更新，而是按照后一個數(shù)據(jù)結構來更新。 SB表示反向算法中的永久標記頂點集合。 CGraph中要 增加 mapVID_listRevEdge。 B）對比 /定量研究 Dijkstra算法和雙向 Dijkstra算法的性能。 2023年春季 通信網(wǎng)絡理論基礎 43 / 70 LabelSetting算法 4 基本 Dijkstra算法 1