資源描述：
《《圖算法及其在通信網(wǎng)中的應用》Dijkstra算法和Dial算法的比較》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。
1、Dijkstra算法和Dial算法的比較李昂2010012010005何慶強2010012010025辜義睿2B輔導老師：王晟、朱永麗—、目錄11122Dijkstra算法和Dial算法的比較三、關鍵詞四、問題描述一、目錄五、求解思路及方法21.Dijkstra算法及偽碼實現(xiàn)22.Dial算法3六、實驗設計31.用Dijkstra算法實現(xiàn)（d（i）代表到節(jié)點1的距離）42.用Dial算法實現(xiàn)4七、實驗結果4八、性能分析41.正確度分析42.復雜度分析5九、結論5十、實驗改進方向及應用5十一、附錄（只寫出主要函數(shù)）61.CP
2、ath類62.DijksiraAlg函數(shù)73.Update函數(shù)84.運行結果8二、弓丨舌在FI常生活中，我們?nèi)绻枰３Ｍ礎地區(qū)和B地區(qū)之間，我們最希槊知道的可能是從A地區(qū)到B地區(qū)間的眾多路徑中，哪一條路徑的路途最短。最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（市結點和路徑組成的）中兩結點之間的最短路徑。Dijkstra（迪杰斯特拉）算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為屮心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法,
3、一般的表述通常冇兩種方式，一種用永久和臨時標號方式，一種是用OPEN,CLOSE表的方式。注意該算法要求圖中不存在負權邊。Dijkstra算法是以起始點為中心向外層層擴展,直到擴展到終點為止,它能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。Dial算法是Dijkstra算法的變體，采用最短路徑搜索技術確定被選擇的路徑，降低了Dijkstra程序里FindMin函數(shù)的復雜度，從而達到加速的目的,提高了算法的效率。三、關鍵詞最短路徑，Dijkstra算法，Dial算法，搜索，加速四、問題描述給定有向加權圖G(
4、V,E),給定源點/起始點s,求從s出發(fā)到V屮其它所有頂點的權重最小的路徑。五、求解思路及方法1.Dijkstra算法及偽碼實現(xiàn)設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合(用S表示，初始時S中只有一個源點，以后每求得一條最短路徑，就將加入到集合S屮，直到全部頂點都加入到S屮，算法就結束了),第二組為其余未確定最短路徑的頂點集合(用U表示)，按最短路徑長度的遞增次序依次把第二組的頂點加入S^o在加入的過程屮，總保持從源點v到S屮各頂點的最短路徑長度不大于從源點v到U中任何頂點
5、的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U屮的頂點的距離，是從v到此頂點只包括S屮的頂點為屮間頂點的當前最短路徑t度。①DijkstraAlg(G(V,E),s)FORallvertexjinVDOd(j)=oo;p(j)=NULL;S={s};d(s)=0;p(s)=NULL;Update(s);WHILESVDOi二FindMin();S=SU⑴；Update(i);ENDWHILE②FindMin()FindvertexvinV-Swhichhasminimumd(
6、v);RETURNv;?Update(i)FOReachedgeeincidenttoiDOIFc.weight+d(i)7、一次找到最小的那個桶開始查找，直到碰到第一個非空的桶為止。桶代表各點到源點的距離，由小到大排列，一個桶里面可以裝多個頂點，即這些點到源點的距離相同。更新時，將指向桶的指針依次往后找，而不需耍從頭開始，節(jié)省了查找的時間，提高了算法效率。六、實驗設計根據(jù)下面的圖求1到6的最短路徑1?用Dijkstra算法實現(xiàn)（d（i）代表到節(jié)點1的距離）1d(2)d(3)d(4)d(5)d(6)122412323123423612345236412345623646實驗程序及結果見附錄2.用Dial算法實現(xiàn)引入若干個桶，桶的編號代表路徑距離，
8、從小到大由左到右排列。此例子理論上應該引入0?24的25個桶，在此，為了方便,僅列出0~6的7個桶。通過從最左端的桶開始月?向右掃描直到找到非空桶，來尋找最小值。更新距離更小時，將節(jié)點盡量往左邊的桶中放。按如下步驟：1—將節(jié)點1放入桶0；12—將節(jié)點2放入桶2,3放入桶4；123—將節(jié)點3從桶4移到桶3
