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

冷思佳

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

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

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

0 前言

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

1 Dijkstra算法含義

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

2 Dijkstra算法原理

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

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

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

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

3.1 優(yōu)化思想

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

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

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

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

3.2.2 算法描述

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

3.3 實(shí)例分析

3.3.1 封閉園區(qū)

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

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

3.3.2 機(jī)場(chǎng)滑行

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

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

3.3.3 應(yīng)急物流

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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