【正文】 能。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 39 / 70 研究性 Project ? 自己設(shè)計(jì)實(shí)驗(yàn)，并通過大量實(shí)驗(yàn)結(jié)果來得出你的結(jié)論。 CGraph中要 增加 mapVID_listRevEdge。 難點(diǎn) 2：要增加數(shù)據(jù)結(jié)構(gòu)。 SB表示反向算法中的永久標(biāo)記頂點(diǎn)集合。 方法 ?P(s,w)+P(w,d) ?P(s,u)+e(u,v)+P(v,d), for all u?SF, v?SB ?上述路徑中具有最小權(quán)重的路徑作為輸出。 ? 注意， CGraph中的 mapVID_listEdge只記錄了出度邊； ? 另外構(gòu)造一 個(gè)數(shù)據(jù)結(jié)構(gòu) ，記錄每個(gè)頂點(diǎn)的入度 邊 :mapVID_listRevEdge； ? 在進(jìn)行 Update時(shí)不按 mapVID_listEdge來更新，而是按照后一個(gè)數(shù)據(jù)結(jié)構(gòu)來更新。 根據(jù) y找到新的桶的位置，做一個(gè) pair，把它插入這個(gè)桶。 Hint 1 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 34 / 70 實(shí)現(xiàn)細(xì)節(jié) 提示 (2/2) //指向桶的迭代器 mapint,mapint, CVertex* ::iterator itBucket。 內(nèi)層的 map的 key是頂點(diǎn) ID。 WHILE S ? V DO i = FindMin()。 S = {s}。換句話說，最多 nC個(gè)桶，F(xiàn)indMin復(fù)雜度為 O(nC)。 b a c d 4 4 1 1 1 e 8 8 不是最佳解。 Na239。要求設(shè)計(jì)一個(gè) CGraph的成員函數(shù)來實(shí)現(xiàn)邊的刪除。 求解思路？ 先刪除 capacity小于 C的邊，然后 在新圖 上調(diào)用 DijkstraAlg。 修改權(quán)重，然后調(diào)用 DijkstraAlg。 Project 給定加權(quán)圖 G，邊上權(quán)重代表通過率。 Project 給出求解單源單宿問題的代碼。 單源單宿最短路問題 最短分離路徑對問題 帶寬約束最短路問題 最大通過率路徑問題 Dijkstra算法擴(kuò)展 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 25 / 70 單源單宿最短路 單源單宿最短路問題 給定加權(quán)圖 G，并給定頂點(diǎn) s和 d，求從 s到 d的最小權(quán)重路徑。 WHILE S ? V DO i = FindMin()。 S = {s}。 hp = v。 i++) { int w = (*i)getWeight()。 listCEdge*::iterator i,iend。 int j = (*())ID。 i++) { if ( isecondID == s) isecondd = 0。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 代碼： DijkstraAlg 17 / 70 void CGraph::DijkstraAlg(int s) { mapint, CVertex*::iterator i,iend。 return FALSE。 p = NULL。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 代碼： Cvertex類 16 / 70 class CVertex{ public: int d。 int getNumVertex()。 public: CGraph(char* inputFile)。 // 所有的頂點(diǎn) mapint, CVertex* mapVID_Vertex。 思路 ? 為每個(gè)頂點(diǎn)準(zhǔn)備一個(gè)記錄關(guān)聯(lián)邊的 list； ? 遍歷并檢查對應(yīng)的頂點(diǎn)是否需要更新。 細(xì)節(jié) ? 使用了哪些 CGraph里的成員變量？ ? 如何設(shè)計(jì)輸出？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 13 / 70 Dijkstra算法代碼設(shè)計(jì) DijkstraAlg d(j)和 p(j) 如何管理 FindMin 從偽碼到 代碼 代碼設(shè)計(jì) 在 CGraph中增加一個(gè) CVertex的 map 創(chuàng)建一個(gè) CVertex類 在 CGraph中增加一個(gè) DijkstraAlg函數(shù) 用一個(gè) list來實(shí)現(xiàn)暫時(shí)標(biāo)記的頂點(diǎn)集合 如何實(shí)現(xiàn) FindMin？ 物理意義：從暫時(shí)標(biāo)記頂點(diǎn)集合（ V – S）中找出距離標(biāo)記最小的頂點(diǎn)。 RETURN v。 Update(i)。 p(s) = NULL。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 9 / 70 怎樣根據(jù)得到的這些信息重構(gòu)出最短路徑？ 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) = ?。 RETURN v。 Update(i)。 p(s)= NULL。 FindMin() Update(i) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 8 / 70 偽碼描述 DijkstraAlg (G(V, E), s) FOR all vertex j in V DO d(j) = ?。 怎么知道誰最近？ 對每個(gè)頂點(diǎn)，都用一個(gè)距離標(biāo)記(Label)來記錄。 2) 連通圖 。通信網(wǎng)絡(luò)理論基礎(chǔ) 王晟 博士 教授 博導(dǎo) Part 05: 最短路算法 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 2 / 70 最短路算法 1 2 LabelSetting算法 LabelCorrecting算法 毫無疑問，重點(diǎn)將是以 Dijkstra算法為代表 的 LabelSetting算法。 所有這些最短路構(gòu)成的是一個(gè) 怎樣的子圖 ？ 樹 ?最短路徑樹 假設(shè) 1) 權(quán)重為正整數(shù) 。 加哪個(gè)頂點(diǎn)？ 從所有與樹鄰接的頂點(diǎn)中，選擇離源點(diǎn)最近的。 頂點(diǎn)的前繼 p(i)。 d(s)=0。 S = S U {i}。 END IF END FOR FindMin () Find vertex v in V – S which has minimum d(v)。 S: 最短路徑樹上的頂點(diǎn)集合。 d(s) = 0。 S = S U {i}。 END IF END FOR FindMin () Find vertex v in V – S which has minimum d(v)。 細(xì)節(jié) ? 如何初始化？ ? 什么時(shí)候需要查詢 /訪問？ 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 12 / 70 Dijkstra算法代碼設(shè)計(jì) DijkstraAlg d(j)和 p(j) 如何管理 從偽碼到 代碼 代碼設(shè)計(jì) 在 CGraph中增加一個(gè) CVertex的 map 創(chuàng)建一個(gè) CVertex類 在 CGraph中增加一個(gè) DijkstraAlg函數(shù) DijkstraAlg函數(shù)放在哪里？ ? option 1：作為一個(gè)獨(dú)立的函數(shù) ? option 2：作為 CGraph的成員函數(shù) 思路 ? 兩種都可以，但前者需要傳入圖對象； ? 為了方便 ，放 在 CGraph里。 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 14 / 70 Dijkstra算法代碼設(shè)計(jì) DijkstraAlg d(j)和 p(j) 如何管理 FindMin Update 從偽碼到 代碼 代碼設(shè)計(jì) 在 CGraph中增加一個(gè) CVertex的 map 創(chuàng)建一個(gè) CVertex類 在 CGraph中增加一個(gè) DijkstraAlg函數(shù) 用一個(gè) list來實(shí)現(xiàn)暫時(shí)標(biāo)記的頂點(diǎn)集合 為每個(gè)頂點(diǎn)準(zhǔn)備一個(gè) CEdge的 list 如何實(shí)現(xiàn) Update？ 物理意義：給定一個(gè)頂點(diǎn)，逐一檢查 /遍歷與它關(guān)聯(lián)的邊。 listCEdge* IncidentList。 Update(int VID)。 ~CGraph()。 }。 CVertex(){d = INFINITY。 bool pVertexComp ( CVertex* x, CVertex* y ) { if ( xd yd ) return TRUE。這里 sort的是對象指針，所以寫了個(gè)外部函數(shù)。 i != iend。 while( ! () ) { (pVertexComp)。 } } 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 代碼： Update 18 / 70 void CGraph::Update(int v) { listCEdge* lEdge = mapVID_listEdge[v]。 i!=iend。 if ( td + w hd ) { hd = td + w。 p(j) = NULL。 Update(s)。 END WHILE 有幾個(gè)循環(huán)？ 2 FOR循環(huán)的操作次數(shù)？ 2n WHILE循環(huán)了幾次？ n WHILE循環(huán)的操作次數(shù)呢？ FindMin ? 從 n個(gè)數(shù)中求最小，復(fù)雜度為 n； ? n+(n1)+…+1 ?n(n1)/2 Update ? 每次循環(huán)檢查的邊的數(shù)目都不同； ? 但是都不重復(fù)； ? 總共檢查了 m次 總的操作次數(shù)為： 2n + n(n1)/2 + n + m 結(jié)論 ： Dijkstra算法 的 復(fù)雜度為 O(n2) 2023年春季 通信網(wǎng)絡(luò)理論基礎(chǔ) 23 / 70 LabelSetting算法 4 基本 Dijkstra算法 1 2 3