基于Dijkstra算法的優(yōu)化策略研究

冷思佳

摘 要：Dijkstra算法不斷改進(jìn)，通過探索最短路徑來處理現(xiàn)實生活中的問題，為生產(chǎn)、生活提供便利。本文簡要介紹Dijkstra算法原理，在此基礎(chǔ)上，重點探究Dijkstra算法優(yōu)化策略，盡可能發(fā)揮這一算法實踐指導(dǎo)作用，希望這一論題能為研究人員提供參考。

關(guān)鍵詞：Dijkstra算法;優(yōu)化;策略分析

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-2064（2019）06-0034-02

0 前言

近年來，智慧交通由于其低成本高效率高可靠性，在封閉園區(qū)、港口等場景下得到了越來越多的應(yīng)用，已經(jīng)成為一種新的趨勢，得到了我國學(xué)者的高度關(guān)注。要實現(xiàn)交通的智慧化，只有在道路數(shù)字化與車輛聯(lián)網(wǎng)化的基礎(chǔ)上，再引入車路協(xié)同的控制機制，由統(tǒng)一的調(diào)度算法來對車輛的行駛進(jìn)行控制，這就離不開Dijkstra算法的研究和優(yōu)化。

1 Dijkstra算法含義

Dijkstra算法，即迪杰斯特拉算法，運用該算法能夠計算出以中心節(jié)點為基礎(chǔ)到達(dá)其他所有節(jié)點的最短路徑。Dijkstra算法是計算最短路徑算法的主要代表，許多學(xué)科中均涉及對它的介紹，例如，圖論、運籌等。Dijkstra算法表現(xiàn)形式分為“永久和臨時標(biāo)號”以及“OPEN，CLOSE”兩種。

2 Dijkstra算法原理

Dijkstra算法是在最短路徑算法的基礎(chǔ)上發(fā)展而來，以無向網(wǎng)絡(luò)為視角，隨著網(wǎng)絡(luò)范圍的不斷變化，最短路徑中的部分節(jié)點固定不變，對此，應(yīng)優(yōu)化算性能，這為Dijkstra算法提供了廣闊空間。Dijkstra算法運行的過程中，以降低復(fù)雜度、縮小節(jié)點范圍為目的，同時，大大提高運行效率，運用新型算法處理節(jié)點問題[1]。

Dijkstra算法為追求最短路徑，利用標(biāo)記法實現(xiàn)這一目標(biāo)，基于源點尋找短節(jié)點，并以新節(jié)點為起點，通過迭代方式尋找段路徑。具體過程：網(wǎng)絡(luò)中設(shè)置集合M和集合N，其中，前者在計算的基礎(chǔ)上融入最短路徑節(jié)點，后者處于最短路徑節(jié)點邊緣處。如果單一節(jié)點yj的對參數(shù)為（Cj.Sj），C是從源節(jié)點y到節(jié)點yj的最短路徑，Sj表示節(jié)點yj在最短路徑的父親節(jié)點。

首先，初始化操作。M=Ф，N包含全部節(jié)點，設(shè)置節(jié)點Cj=∞，Sj=[.]。其次，yj加入集合M，并從N中刪除，設(shè)置Cs=0，Ss∈Ф。然后，檢驗M中節(jié)點yi到N中節(jié)點yj的距離Lij，需要注意的是，yi與yj應(yīng)保持連接狀態(tài)，設(shè)置Cj=min[Cj，Ci+Lij]。接下來選取Cj最小節(jié)點yj，并從N集合中刪除，將其融入集合M，此時形成的節(jié)點即最短路徑新節(jié)點（x）。最后尋找x的父親節(jié)點Sj，具體記錄節(jié)點參數(shù)（Cj.Sj）。待網(wǎng)絡(luò)節(jié)點加入到M集合后，這時N=Ф，Dijkstra算法原理整個過程順利完成[2]。

3 Dijkstra算法優(yōu)化策略

3.1 優(yōu)化思想

Dijkstra算法要滿足智慧交通多車輛并發(fā)的要求，就需要考慮對算法進(jìn)行優(yōu)化，通過滲透優(yōu)先隊列改進(jìn)算法確定優(yōu)先級，因此，能夠自行設(shè)置起點，合理調(diào)整頂點優(yōu)先級。據(jù)調(diào)查可知，優(yōu)先隊列有效運用，能夠在一定程度上降低算法復(fù)雜度，大大提高算法效率。為簡化起見，本文僅討論針對單一車輛終端的調(diào)度算法優(yōu)化，多車輛并發(fā)所涉及到的多線程調(diào)度等不再本文討論范圍內(nèi)。

3.2 優(yōu)化設(shè)計

3.2.1 設(shè)置參數(shù)

在加權(quán)無向網(wǎng)絡(luò)中，的V和E分別表示節(jié)點集合和邊集合，節(jié)點用n表示，邊用m表示。G中節(jié)點用u表示，節(jié)點間的邊用e表示，權(quán)值用表示。最短路徑數(shù)用表示，其中，、、分別表示根節(jié)點到節(jié)點最短路徑距離、父親節(jié)點、根節(jié)點最短路徑節(jié)點集合。針對加權(quán)無向網(wǎng)絡(luò)內(nèi)部節(jié)點設(shè)置狀態(tài)參量，狀態(tài)參量表示為，該向量值為1時，意味著節(jié)點數(shù)值保持不變，無需處理。當(dāng)該向量值為0時，意味著節(jié)點應(yīng)不斷更新。

3.2.2 算法描述

網(wǎng)絡(luò)G中，根節(jié)點成功構(gòu)造，如果其中某邊的權(quán)值動態(tài)變化，那么應(yīng)確定受影響的范圍。針對算法描述時，應(yīng)細(xì)分兩種情況，第一種情況即權(quán)值增大，第二種情況即權(quán)值減小。當(dāng)權(quán)值增大時：如果SPT的邊權(quán)值并未增大，那么各節(jié)點最短路徑的長度已經(jīng)達(dá)到最小，所以對于SPT的結(jié)構(gòu)沒有影響;如果SPT的邊權(quán)值增大，那么網(wǎng)絡(luò)中的位置就可能不是路徑最短的位置，所以需要及時調(diào)整節(jié)點的位置。當(dāng)權(quán)值減小時：如果SPT的邊權(quán)值并未減小，需要比較發(fā)生變化的邊對應(yīng)節(jié)點的最短路徑，必要時可以修改其中一個節(jié)點的父親節(jié)點;如果SPT的邊權(quán)值減小，則需要找到子節(jié)點，在其他節(jié)點的最短路徑發(fā)生“聚集”時，確定權(quán)值變更的影響范圍。這里需要注意的是，如果更新節(jié)點最短路徑的值變小，那么就會影響與之相連的節(jié)點，所以需要考慮各個節(jié)點對應(yīng)的項，一般都將這些項歸入一個集合中。

3.3 實例分析

3.3.1 封閉園區(qū)

Dijkstra算法應(yīng)用于封閉園區(qū)（例如港口）的調(diào)度規(guī)劃，以往港口場地選址方法主要為經(jīng)驗數(shù)據(jù)法，這種方法實際應(yīng)用時，方法的時效性較低，且易與經(jīng)驗數(shù)據(jù)直線距離存在偏差。同時，多臺車輛并發(fā)處理不同任務(wù)安排時，通行規(guī)劃會產(chǎn)生相互之間的影響，這些因素導(dǎo)致調(diào)度準(zhǔn)確性大大降低，這與車輛沿港內(nèi)道路行駛的實際需求存在偏差。應(yīng)用Dijkstra算法完成集卡調(diào)度場選址任務(wù)，在這一過程中，合理確定起點和終點，同時，確定路徑算法節(jié)點，求得最短路徑算法，大大提高調(diào)度場選址準(zhǔn)確性。

Dijkstra算法應(yīng)用分析：設(shè)置權(quán)有相圖M=（），在其中包括道路節(jié)點數(shù)量以及距離，針對頂點集合以及節(jié)點路徑具體分析。首先，集合M僅包括源點，即M=源點，節(jié)點間距離為0。集合P包括除源點外所有頂點，以及節(jié)點距離。其次，從集合P中選擇距離源點最小頂點集合融入到M中，并重復(fù)這樣的操作，進(jìn)而能夠得出源點到不同節(jié)點的最短距離。然后，以目的點距離為出發(fā)點，針對源點和目的點的中間點全面記錄，與此同時，適時調(diào)整集合P中頂點距離，如果源點與頂點間距離小于初始距離，那么將源點與頂點距離設(shè)置為最短距離。最后，重復(fù)上述操作，待所有頂點融入到集合M中。

3.3.2 機場滑行

Dijkstra算法應(yīng)用于機場滑行（例如海口美蘭國際機場），美蘭機場是我國4E級國際機場，美蘭機場單跑道長度是3600m，寬度是45m，真方位角是90與270度。飛機滑行網(wǎng)絡(luò)包括機坪滑行道、主滑行道、快速脫離滑行道與停機坪滑行道。該機場由17個近停機位、16個遠(yuǎn)停機位共計33個停機位組成。美蘭機場的飛機起降操作原則是中型機從R6口脫離跑道，大型機從R5口脫離跑道。本案例選擇2016年8月份某日07：50到13：30的航班時刻運用Dijkstra進(jìn)行優(yōu)化計算，探究Dijkstra在確定機場最短滑行路徑方面的作用。

Dijkstra算法應(yīng)用分析：設(shè)置G=指代機場滑行路徑，w>0是滑行道的權(quán)，G指代中心節(jié)點，V指代最短路徑，采用雙標(biāo)號方法，引進(jìn)計算步驟r≥0，通過逐步獲取標(biāo)號計算出最短路徑。通過對于美蘭機場實際滑行路徑所消耗的時間、資源與Dijkstra算法下航空器消耗的時間、資源得出Dijkstra算法下降低了130kg資源，時間減少了160s，在航班沖突處運用該算法能夠提前進(jìn)行規(guī)劃，并選擇最佳路徑。

3.3.3 應(yīng)急物流

Dijkstra算法也常常需要在應(yīng)急物流路徑規(guī)劃中得到應(yīng)用，需要將時間當(dāng)成是路徑規(guī)劃的首要目標(biāo)。不同于常規(guī)情況，應(yīng)急物流不將路程當(dāng)成是路徑規(guī)劃問題的權(quán)重，而是以時間為道路權(quán)重。在某地突發(fā)事件中，要求將應(yīng)急物資從應(yīng)急倉庫v1運送到需求點v7，之間經(jīng)過5個道路節(jié)點，即v2-v6，應(yīng)急車輛可雙向行駛，要求通過車輛路線規(guī)劃在最短時間內(nèi)完成物資運輸。在遙感衛(wèi)星支持下，道路一旦中斷物流指揮控制中心可以進(jìn)行路況把握，指揮車輛改變行駛道路。

在算法應(yīng)用過程中，可以將路線規(guī)劃問題描述為從倉庫到物資運送需求點共包含7個階段，構(gòu)成了包含有限條道路的通道。在車輛通過各道路所需時間已知的情況下，對道路中斷概率和概率密度分布進(jìn)行考慮，搜索時間最短的路徑。由于各道路中斷時間概率密度函數(shù)服從均勻分布，同時道路中斷點距離上一節(jié)點需要時間同樣均勻分布，因此可以采用優(yōu)化Dijkstra算法進(jìn)行路徑規(guī)劃，先對起點v1到點vj權(quán)值和T1j進(jìn)行初始化，然后對點到該點連通未計算的點的權(quán)值進(jìn)行計算，從未計算點中進(jìn)行T1j最小點的選取，直至完成所有節(jié)點計算可以實現(xiàn)最短時間的路徑搜索。應(yīng)用優(yōu)化算法得到路徑為1→3→6→7，需要9h時間達(dá)到需求點。相較于經(jīng)典Dijkstra算法，能夠縮短12.9%的時間。由此可見，在應(yīng)急物流路徑規(guī)劃中應(yīng)用Dijkstra算法，可以使運輸時間得到有效縮短。

3.4 算法改進(jìn)分析

3.4.1 算法應(yīng)用問題

從算法應(yīng)用情況來看，在網(wǎng)絡(luò)節(jié)點較少的情況下，采用Dijkstra算法核心步驟就是從未選定為最短距離的網(wǎng)絡(luò)節(jié)點中進(jìn)行當(dāng)前集合中權(quán)值最小的點的選擇，需要實現(xiàn)步驟的循環(huán)操作。在網(wǎng)絡(luò)節(jié)點較多的情況下，不采用比較篩選策略需要對未標(biāo)記的點進(jìn)行循環(huán)比較，最終導(dǎo)致最優(yōu)路徑計算速率受到制約。受這一因素的影響，在網(wǎng)絡(luò)節(jié)點數(shù)量較大時程序正確性難以得到有效把握，將導(dǎo)致節(jié)點操作性較差，不利于算法的應(yīng)用。

3.4.2 算法改進(jìn)建議

針對算法應(yīng)用問題，需要采用添加網(wǎng)絡(luò)節(jié)點標(biāo)記flag的方式進(jìn)行算法改進(jìn)，使算法應(yīng)用效果得到保證。具體來講，就是利用布爾值類型數(shù)組flag實現(xiàn)算法節(jié)點標(biāo)記。在網(wǎng)絡(luò)節(jié)點被選定為最短距離的情況下，需要進(jìn)行ture標(biāo)記，否則進(jìn)行flase標(biāo)記。在初始化操作的過程中，需要將所有節(jié)點標(biāo)記為flase。隨著算法的進(jìn)行，逐步完成選定節(jié)點的修改，能夠在循環(huán)操作完成后實現(xiàn)所有節(jié)點標(biāo)記，得到節(jié)點對應(yīng)flag標(biāo)記值。針對未選定節(jié)點進(jìn)行最小權(quán)值的篩選，由于選定節(jié)點均標(biāo)記為ture，因此只要進(jìn)行false值節(jié)點選擇就能迅速完成目標(biāo)查找。除了對節(jié)點進(jìn)行標(biāo)記，針對為確定最短距離的網(wǎng)絡(luò)節(jié)點，可以進(jìn)行數(shù)值標(biāo)記。在實際操作中，可以利用整型變量min進(jìn)行標(biāo)記，從而通過比較實現(xiàn)最小距離的篩選。在初始化操作中，可以將min定義成最大值。在數(shù)組遍歷的過程中，min將不斷減小。實際進(jìn)行節(jié)點判別時，應(yīng)當(dāng)確保節(jié)點flag標(biāo)記值為flase，同時還要確保min當(dāng)前min要小，才能完成網(wǎng)絡(luò)節(jié)點重新賦值，同時對當(dāng)前節(jié)點標(biāo)記號進(jìn)行記錄。如果不能同時滿足這兩個條件，可以直接跳過。采用該種方法，只需要一次循環(huán)就能在每次搜索中進(jìn)行未標(biāo)記網(wǎng)絡(luò)節(jié)點最小權(quán)值的查找，因此能夠使算法效率得到提高。采用改進(jìn)后的算法進(jìn)行路徑規(guī)劃可以發(fā)現(xiàn)，無論是在交通管理還是物流疏散等方面，算法都能得到快速執(zhí)行。出現(xiàn)這種情況，與算法節(jié)點計算量的減少有關(guān)，因此采用優(yōu)化算法能夠獲得較好應(yīng)用前景。

4 結(jié)語

綜上所述，Dijkstra算法優(yōu)化后，算法性能會大大提高，能夠為節(jié)點變化情況作出詳細(xì)解釋，并在短時間內(nèi)提供最優(yōu)路徑，同時，算法研究人員能夠以此為借鑒，在理論補充的前提下，為實踐活動提供理論指導(dǎo)。此外，Dijkstra算法應(yīng)用前景會越來越廣闊，能為生活中實際問題處理提供理論依據(jù)，因此，研究學(xué)者應(yīng)深入探究，為Dijkstra算法改進(jìn)提供思路和建議。

參考文獻(xiàn)

[1] 房敏.淺談Dijkstra算法的相關(guān)改進(jìn)[J].計算機產(chǎn)品與流通，2017（10）：212.

[2] 盧飛.基于Dijkstra算法的集裝箱港口集卡調(diào)度場規(guī)劃研究[J].中國水運，2017（01）：48-49.

[3] 王樹西，李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機科學(xué)，2014，41（6）：217-224.