西安科技大學通信學院Dijkstra最短路徑算法摘要OSPF是由IETF的IGP工作組為IP網開發的一種能適應大型網絡需要的典型的鏈路狀態路由協議，它可以迅速地檢測AS內的拓撲變化，經過一個比較短的收斂期后，重新計算出無環路由。在OSPF中采用的是Dijkstra算法來實現最短路徑的計算，做到了選路的高效、可靠。不同的算法在時間上的開銷是不一樣的，可能會有很大的差別，而對于一個大型的網絡來講，選路的效率往往就是網絡的生命，算法的重要性不言而喻。關鍵詞OSPF最短路徑Dijkstra算法將網絡結點分成3部分：未標記結點、臨時標記結點和永久標記結點．網絡中所有結點首先初始化為未標記結點，在搜索過程中和最短路徑中的結點相連通的結點為臨時標記結點，每次循環都是從臨時標記結點中搜索距源點路徑長度最短的結點作為永久標記結點，直至找到目標結點或者所有的結點都成為永久標記結點來結束算法．假設每個點都有一對標號（,），其中是從起源點到點的最短路徑的長度（從頂點到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；則是從到的最短路徑中點的前一點．求解從起源點到點的最短路徑算法的基本過程如下：（1）初始化．起源點設置為：①,為空；②所有其他點:,；③標記起源點，記,其他所有點設為未標記的．（2）檢驗從所有已標記的點到其直接連接的未標記的點j的距離，并設置：式中，是從點到的直接連接距離．（3）選取下一個點．從所有未標記的結點中，選取中最小的一個：，（所有未標記的點），點就被選為最短路徑中的一點，并設為已標記的．（4）找到點的前一點．從已標記的點中找到直接連接到點的點，作為前一點，設置：=．0（5）標記點．如果所有點已標記，則算法完全推出，否則，記=，轉到（2）再繼續．010010010414130105060322032圖2-1Dijkstra算法最短路徑應用演示圖循環紅點集初始化-01030100110106030100230105030903201050306044010503060表2-10節點到4節點的最短路徑2.3Dijkstra算法的優缺點Dijkstra算法能夠保證100%找到最優解，但其搜索速度較慢，搜索效率非常低，時間花費較多，一般只能用于離線的路徑規劃問題．如節點數為的圖，用Dijkstra算法計算最短路徑總共需要迭代次，每次迭代都新加一個節點到臨時節點集合中，由于第i次迭代時不在臨時節點集合中的節點數為．即第次迭代需對個節點進行處理，因此其所需的處理數為：對n個節點網絡的時間復雜度是．在實際應用當中，使用Dijkstra算法查找最短路徑時耗費大量的時間進行數據的比較，本文對Dijkstra算法進行分析，通過改變算法實現減少不必要節點計算的時間，提高算法的效率達到對其進行優化．第3章基于Dijkstra算法的優化算法的研究3.1幾種優化算法3.1.1減小算法中成功搜索的搜索范圍減小算法中成功搜索的搜索范圍以盡快到達目標節點．在對現實問題中的交通圖初始化為網絡拓撲圖時，雖然終點已知，而源點尚未確定，但依據常識離案發地段最近的派出所應為案發地段所在轄區派出所，或其周邊派出所，也就是源點的選取范圍可以確定．利用MapObjects2組件提供的MapLayer.SearchExpression（expression）記錄集篩選方法，根據案發地段（終點）的不同，動態選取案發地段所在轄區及相鄰轄區的道路圖層及派出所圖層數據進行最短路徑查詢，從而有效地減少了拓撲圖中節點總數的值．3.1.2改進算法的存儲結構在實際工作中，還要建立起空間數據結構．網絡數據結構使用的是“邊和節點”的數據結構，該數據結構是建立在圖論的基礎上，節點可用來定義邊的連接關系．對于網絡數據的存儲，傳統的是采用圖論中的鄰接矩陣方法，其存儲量為(為網絡中節點數)．通常的地理網絡，盡管節點很多，但與節點相關聯的節點數目并不多，一般都為稀疏圖，將會浪費大量的空間．若采用鄰接表的鏈式存儲結構，其存儲量為(為節點列表中，同節點關聯的所有邊的數目)，可節省大量的存儲空間，尤其是在表示與節點和邊相關信息較多的地理網絡時，更為有效．但鄰接表卻難以判斷兩節點之間的關系，因此本文提出利用．NET框架提供的特殊類Hashtable．NET框架包含特殊類，比如通常所說的集合類用于存儲對象．與數組類似，集合類可以把對象放入容器中，然后再取出．但集合的使用方法與數組不同，擁有用于插入和刪除項的專用方法．使用Hashtable最大的優點就是大大降低數據存儲和查找的時間花費．3.2本文對Dijlstra優化算法研究3.2.1優化目標Dijkstra算法用來求解圖上從任一節點(源點)到其余各節點的最短路徑．其時間復雜度為；采用鄰接矩陣存儲網絡拓撲結構，需要的存儲空間，隨著節點數的增大，其計算效率和存儲效率越低．針對此問題，提出了Dijkstra算法的改進，本文在對傳統Dijkstra算法分析的基礎上，對其進行了優化，優化算法只對最短路徑上節點的鄰居做處理，而不涉及到其他節點．3.2.2優化思路Dijkstra算法基本方法：設是從源點s到節點j的最短路徑長度；是從到的最短路徑中點的前一節點．是標識集合；是未標識集合；是節點集合．是節點到節點的距離（與直接相連，否則）．算法步驟如下：Step0：；；（，與直接相連）或(，與不直接相連)．Step1：在中找到節點，使到的距離最小，并將劃歸到（可從與直接相連的中考慮）若=min，與直接相連，則將劃歸到中，即，；；．Step2：修改中節點的值：；若值改變，則．；.Step3：選定所有的最小值，并將其劃歸到中：；；；若,所有節點已標識，則算法終止，否則，轉入Step2．通過分析傳統Dijkstra算法的基本思路，傳統Dijkstra算法存在如下兩點不足：（1）當從未標記節點集合T中選定一個節點作為轉接點后時，需掃描未標記節點集合中的節點并更新其值，而未標記節點集合中往往包含大量與轉接節點不直接相連的節點（即）；（2）在未標記節點集合中選擇一個值最小的節點作為下一個轉接節點，然而下一個轉接節點往往是與標記節點集合中的節點直接相連的．第4章結束語目前提出的此類最短路徑的算法大約有17種,其中三種效果比較好,即TQQ(graphgrowthwithtwoqueues)、DKA(theDijkstrasalgorithm_implementedwithapproximatebuckets)及DKD(theDijkstrasalgorithm_implementedwithdoublebuckets)。后兩種算法是基于Dijkstra的算法,更適合于計算兩點間的最短路徑問題。總體來說,這些算法所采用的數據結構及其實現方法由于受到當時計算機硬件發展水平的限制,將空間存儲問題放到了一個很重要的位置,以犧牲適當的時間效率來換取空間節省。目前,空間存儲問題已不是要考慮的主要問題,因此有必要對已有的算法重新進行考慮并進行改進,可以用空間換時間來提高最短路徑算法的效率。最短路徑分析過程在網絡分析中扮演著重要的角色,但由于過去的分析算法較復雜,開銷較多,因而本文通過對經典Dijkstra算法的改進,使用完全二叉樹結構來實現優先級隊列的操作,在一定程度上優化了最短路徑的計算過程,并降低了算法的時間復雜度,使時間復雜度達到O(ElgN),實際數據測試也表明了該算法的可行性。參考文獻[1]王峰．Dijkstra及基于Dijkstra的前N條最短路徑算法在智能交通系統中的應用[J]．計算機應用