1、Dijkstra最短路徑算法摘要OSPF是由IETF的IGP工作組為IP網開發的一種能適應大型網絡需要 的典型的 鏈路狀態路由協議，它可以迅速地檢測 AS 內的拓撲變化，經過一個 比擬短的收斂期 后，重新計算出無環路由。在 OSPF 中采用的是 Dijkstra 算 法來實現最短路徑的計算， 做到了選路的高效、可靠。不同的算法在時間上的 開銷是不一樣的，可能會有很大 的差異，而對于一個大型的網絡來講，選路的 效率往往就是網絡的生命，算法的重 要性不言而喻。關鍵詞 OSPF 最短路徑 Dijkstra第 1 章 緒論最短路徑算法是電腦科學與地理信息科學等領域研究的熱點， 其算法有很多 種，其中傳

2、統的 Dijkstra 算法一般用于計算一個源節點到所有其他節點的最小 代價路徑， 并且能夠適應網絡拓撲的變化， 性能穩定， 因而可以在運輸路線規劃 等領域都應用廣泛1.1 國內外最短路徑算法的開展及其概況最短路徑在 20世紀初開始受到人們的重視， 關于它的求解方法， 當時有很多 科學家在研究但給出求解的根本思想的人直到1959年才出現，是一位名叫Edsger WybeDijkstra 迪杰斯特拉的荷蘭電腦科學家，他不僅給出了求解的 根本思想，還給出了算法他給出的算法主要解決的問題是從某一個固定的點到 其他各點的最短路徑問題后來這個算法被譽為一代經典，被稱作 Dijkstra 算 法后來， 人

3、們逐漸從兩個方面來研究最短路徑， 分為完全信息情況下和不確定 情況下確定情況下對最短路徑的研究的過程中， 開展出了很多高效的算法， 其 中1958年的Bellman算法、1959年的Dijkstra 算法、1969年的Dreyfus算法已成為 確定情況下的經典算法 1 而不確定情況下對最短問題的研究又分成了四個方 面：研究路段長度隨機變化的最短路徑問題，以Frank和Mirchandani為代表；研究不同費用函數最短路徑問題， 以Loui、Muethy和Sarkar為代表；研究時間獨立 情況下的路段長度隨機變化的最短路徑問題， Hall 、 LiPing Fu 、 L.R.Rilett 、 E

4、lise和Hani為代表；研究路段長度為區間范圍的最短路徑問題，以Toma和Rajeev為代表.其中，第二方面問題的研究得出的結論是“當目標是期望最短路 徑時問題轉化為將邊的權重用期望值表示的最短路徑問題1.2 傳統 Dijkstra 算法仍然存在的一些問題原始 Dijkstra 算法在存儲圖形數據和運算時，基于網絡的權矩陣，需要根 據其節點與距離之間的關系，形成關聯矩陣、鄰接矩陣與距離矩陣，需要定義 N N 的數組來存儲數據， 其中 N 為網絡的節點數， 當網絡的節點數較大時， 將 占用大量的電腦內存原始 Dijkstra 算法在運行時一般將網絡節點分為未標記節點、臨時標記節點和 永久標記節

5、點 3 種類型網絡中所有節點首先初始化為未標記節點， 在搜索過程 中和最短路徑節點相連通的節點為臨時標記節點， 每一次循環都是從臨時標記節 點中搜索距離原點路徑長度最短的節點作為永久標記節點， 直至找到目標節點或 者所有節點都成為永久標記節點才結束算法 根據算法的描述可知對臨時標記節 點的遍歷成為 Dijkstra 算法的瓶頸，影響了算法的執行效率第 2 章 Dijkstra 經典算法2.1 引言Dijkstra 算法是典型最短路算法，用于計算一個節點到其他所有節點的最 短路徑主要特點 是 以起始 點 為中心 向外層層擴 展，直 到擴展到終 點為 止 Dijkstra 算法能得出最短路徑的最優

6、解，但由于它遍歷計算的節點很多， 所以效率低 如何改進這一經典算法， 成為了實現圖論中賦權圖中解決實際問題 的重要課題2.2 原理及應用Dijkstra 迪杰斯特拉 算法是典型的單源最短路徑算法， 用于計算一個節點 到其他所有節點的最短路徑 主要特點是以起始點為中心向外層層擴展， 直到擴 展到終點為止 Dijkstra 算法是很有代表性的最短路徑算法，在很多專業課程 中都作為根本內容有詳細的介紹，如數據結構，圖論，運籌學等等 Dijkstra 一般的表述通常有兩種方式， 一種用永久和臨時標號方式， 一種是用 OPEN,CLOSE 學習文檔 僅供參考表的方式，這里均采用永久和臨時標號的方式該算法

7、要求圖中不存在負權邊2.2.1 原理Dijkstra算法是1959年由E. W Dijkstra提出的圖論中求最短路徑的一個著 名的算法，使用其可以求得圖中一點到其他各頂點的最短路徑 原始的 Dijkstra 算法將網絡結點分成 3局部：未標記結點、臨時標記結點和永久標記結點網絡 中所有結點首先初始化為未標記結點， 在搜索過程中和最短路徑中的結點相連通 的結點為臨時標記結點， 每次循環都是從臨時標記結點中搜索距源點路徑長度最 短的結點作為永久標記結點， 直至找到目標結點或者所有的結點都成為永久標記 結點來結束算法假設每個點都有一對標號Wj, Pj，其中Wj是從起源點s到點j的最短路 徑的長度從

8、頂點到其本身的最短路徑是零路 沒有弧的路 ，其長度等于零 ； Pj那么是從s到j的最短路徑中j點的前一點.求解從起源點i到點j的最短路徑 算法的根本過程如下：1初始化.起源點設置為：Ws 0, Ps為空；所有其他點：Wi, Pi?;標記起源點s，記k s,其他所有點設為未標記的.2檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置:Wj mi nWj,Wk dkj式中，dkj是從點k到j的直接連接距離.3選取下一個點.從所有未標記的結點中，選取Wj中最小的一個i :W min Wj，所有未標記的點j，點i就被選為最短路徑中的一點，并設為 已標記的4找到點 i 的前一點從已標記的點中

9、找到直接連接到點 i 的點 j ，作為前一點，設置： i= j5標記點i .如果所有點已標記，那么算法完全推出，否那么，記 k=i，轉到502再繼續.圖2-1 Dijkstra算法最短路徑應用演示圖循環紅點集SKD0D1D2D3D4初始化0-0103010010,11010603010020,1,3301050309030,1,3,2201050306040,1,32,44010503060表2-1 0節點到4節點的最短路徑2.3 Dijkstra 算法的優缺點Dijkstra 算法能夠保證100%®到最優解，但其搜索速度較慢，搜索效率非 常低，時間花費較多，一般只能用于離線的路徑規

10、劃問題.如節點數為n的圖，用Dijkstra算法計算最短路徑總共需要迭代n 1次，每 次迭代都新加一個節點到臨時節點集合中，由于第i次迭代時不在臨時節點集合中的節點數為n i .即第i次迭代需對n i個節點進行處理，因此其所需的處理 數為：(ni 1i)n(n 1)2對n個節點網絡的時間復雜度是 0(n2).在實際應用當中，使用Dijkstra 算 法查找最短路徑時消耗大量的時間進行數據的比擬，本文對 Dijkstra 算法進行 分析，通過改變算法實現減少不必要節點計算的時間， 提高算法的效率到達對其 進行優化.第3章 基于Dijkstra算法的優化算法的研究3.1 幾種優化算法3.1.1 減

11、小算法中成功搜索的搜索范圍減小算法中成功搜索的搜索范圍以盡快到達目標節點.在對現實問題中的交通圖初始化為網絡拓撲圖時，雖然終點，而源點尚未確定，但依據常識離案 發地段最近的派出所應為案發地段所在轄區派出所，或其周邊派出所，也就是源點的選取范圍可以確定.利用MapObjects2組件提供的 MapLayer.SearchExpression expression丨記錄集篩選方法，根據案發地段終 點的不同，動態選取案發地段所在轄區及相鄰轄區的道路圖層及派出所圖層數 據進行最短路徑查詢，從而有效地減少了拓撲圖中節點總數n的值"I .3.1.2 改進算法的存儲結構在實際工作中，還要建立起空間

12、數據結構.網絡數據結構使用的是“邊和節點的數據結構， 該數據結構是建立在圖論的根底上， 節點可用來定義邊的連接 關系對于網絡數據的存儲， 傳統的是采用圖論中的鄰接矩陣方法， 其存儲量為 N NN為網絡中節點數通常的地理網絡，盡管節點很多，但與節點相關聯 的節點數目并不多， 一般都為稀疏圖， 將會浪費大量的空間 假設采用鄰接表的 鏈式存儲結構，其存儲量為E E為節點列表中，同節點關聯的所有邊的數目， 可節省大量的存儲空間，尤其是在表示與節點和邊相關信息較多的地理網絡時， 更為有效但鄰接表卻難以判斷兩節點之間的關系，因此本文提出利用.NET匡架提供的特殊類Hashtable . NET匡架包含特殊

13、類，比方通常所說的集合類用于存 儲對象與數組類似，集合類可以把對象放入容器中，然后再取出但集合的使 用方法與數組不同，擁有用于插入和刪除項的專用方法使用 Hashtable 最大的 優點就是大大降低數據存儲和查找的時間花費 8 3.2 本文對 Dijlstra 優化算法研究3.2.1 優化目標Dijkstra 算法用來求解圖上從任一節點 源點 到其余各節點的最短路徑其時間復雜度為0n2;采用鄰接矩陣存儲網絡拓撲結構，需要N N的存儲空間，隨著節點數 N 的增大，其計算效率和存儲效率越低針對此問題， 提出了 Dijkstra 算法的改進， 本文在對傳統 Dijkstra 算法分析的根底上， 對其

14、 進行了優化，優化算法只對最短路徑上節點的鄰居做處理， 而不涉及到其他節點3.2.2 優化思路Dijkstra算法根本方法：設Wj是從源點s到節點j的最短路徑長度；Pj是從 s到j的最短路徑中j點的前一節點.S是標識集合；T是未標識集合；M是節 點集合.dij是節點i到節點j的距離i與j直接相連，否那么dij .算法步 驟如下：StepO: S s ; T M S ; Wj dj j T , s與 j 直接相連或 Wjj T , s與j不直接相連.Stepl:在T中找到節點i，使s到i的距離最小，并將i劃歸到S可從與s直 接相連的j中考慮假設dsi= min dsj ，j與s直接相連，那么將i

15、劃歸到S中，即S s, i ，T T i ； j T ； P S Step2 :修改T中j節點的Wj值：Wj min Wj, Wi dj ;假設Wj值改變，那么 R i . j T ； i S.Step3 :選定所有的Wj最小值，并將其劃歸到S中：Wi mi nWj; S S i ; T T i ;假設s n,所有節點已標識，那么算法終止，否那么，轉入Step2.通過分析傳統Dijkstra算法的根本思路，傳統Dijkstra算法存在如下兩點不 足：1當從未標記節點集合TT中選定一個節點k作為轉接點后時，需掃描未 標記節點集合T中的節點j并更新其Wj值，而未標記節點集合T中往往包含大量 與轉接

16、節點k不直接相連的節點i即dkj ；2在未標記節點集合T中選擇一個w值最小的節點作為下一個轉接節點，然而下一個轉接節點往往是與標記節點集合S中的節點直接相連的.第4章結束語目前提出的此類最短路徑的算法大約有17種，其中三種效果比擬好，即TQQ (graph growth with two queues) 、DKA (the Dijkstra 1 s algori thm_ implemented with approximate buckets)及 DKDfthe Dijkstra * s algori thm_ implemented with double bucket s)。后兩種算法是基于 Dijkstra 的算法，更 適合于計算兩點間的最短路徑問題。總體來說，這些算法所采用的數據結構及其實現方法由于受到當時電腦硬件開展水平的限制，將空間存儲問題放到了一個很重要的位置，以犧牲適當的時間效率來換取空間節省。目前，空間存儲問題 已不是要考慮的主要問題，因此有必要對已有的算法重新進行考慮并進行改進，可以用空間換時間來提高最短路徑算法的效率。最短路徑分析過程在網絡分析中扮演著重要的角色 ，但由于過去的分析算法 較復雜，開銷較多，因而本文通過對經典 Dijkstra 算法的改進，使用完全二 叉樹結構來實現優先級隊列的操作，在一定程度上優化了最短路徑的計算過程， 并降