最短路算法(圖論)ppt課件.ppt

《最短路算法(圖論)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、圖算法及其在通信網中的應用王晟博士教授博導Part05:最短路算法2009年春季圖算法及其在通信網絡中的應用2/55最短路算法12Label-Setting算法Label-Correcting算法毫無疑問，重點將是以Dijkstra算法為代表的Label-Setting算法。3All-Pair最短路算法2009年春季圖算法及其在通信網絡中的應用3/55Label-Setting算法4基本Dijkstra算法1235分析(Analysis)擴展(Extension)加速(Speedup)應用(Application)2009年春季圖算法及其在通信網絡中的應用4/55基本Dijks

2、tra算法Dijkstra算法是本課程的核心內容，務必要掌握其思想和具體的編程方法。問題分析代碼設計算法示例求解思路偽碼描述Dijkstra算法2009年春季圖算法及其在通信網絡中的應用5/55問題描述單源最短路問題給定有向加權圖G(V,E)，給定源點/起始點s，求從s出發(fā)到V中其它所有頂點的權重最小的路徑。所有這些最短路構成的是一個怎樣的子圖？樹?最短路徑樹假設權重為正整數(shù);連通圖;存在多條最短路時,只求1條.為什么一定是樹？最短路上的子路徑也是最短路最短路徑樹是生成樹么？是的最短路徑樹是最小生成樹么？不一定ASBC11221ASBC122ASBC1212009年春季圖算法及

3、其在通信網絡中的應用6/55Dijkstra的求解思路算法思路逐步地發(fā)展最短路徑樹，直至它覆蓋所有頂點。怎樣實現(xiàn)？構造一個循環(huán)，每次循環(huán)都增加一個頂點到最短路徑樹上。加哪個頂點？從所有與樹鄰接的頂點中，選擇離源點最近的。怎么知道誰最近？對每個頂點，都用一個距離標記(Label)來記錄。哪里來的距離標記？每次循環(huán)都需要對距離標記進行更新。如何維護最短路徑樹？如何選擇頂點？如何更新距離標記？樹上頂點的集合S。頂點的前繼p(i)。FindMin()Update(i)2009年春季圖算法及其在通信網絡中的應用7/55偽碼描述DijkstraAlg(G(V,E),s)FORallvert

4、exjinVDOd(j)=?;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILES?VDOi=FindMin();S=SU{i};Update(i);ENDWHILEUpdate(i)FOReachedgeeincidenttoiDOIFe.weight+d(i)

5、最短路徑樹上的前繼點。S:最短路徑樹上的頂點集合。2009年春季圖算法及其在通信網絡中的應用8/55怎樣根據(jù)得到的這些信息重構出最短路徑？Dijkstra算法示例?saedbc241423322?????0cs2,s4,sDijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=?;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILES?VDOi=FindMin();S=SU{i};Update(i);ENDWHILEUpdate(i)FOReachedgeeincidenttoiDOIFe.weight

6、+d(i)

7、何改進代碼？2009年春季圖算法及其在通信網絡中的應用9/55Dijkstra算法代碼設計DijkstraAlgd(j)和p(j)如何管理FindMinUpdate從偽碼到代碼如何實現(xiàn)d(j)和p(j)Option1：單獨用數(shù)組/vector來實現(xiàn)；Option2：創(chuàng)建一個CVertex類來記錄；思路兩個方法都可以；使用類便于擴展，也便于封裝。細節(jié)構造函數(shù)？接口函數(shù)？代碼設計在CGraph中增加一個CVertex的map創(chuàng)建一個CVertex類在CGraph中增加一個DijkstraAlg函