Dijkstra最短路徑算法

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