應(yīng)急資源配送中Dijkstra改進算法的研究

石曉達　孫連英　葛娜　趙平　李子元

[摘要]路徑規(guī)劃問題是應(yīng)急資源配送中的核心問題，最短路徑算法在路徑規(guī)劃過程中起著決定性的作用，在眾多路徑規(guī)劃算法中最經(jīng)典且最具代表性的就是Dijkstra算法。以傳統(tǒng)的Dijkstra算法分析為基礎(chǔ)，從存儲結(jié)構(gòu)和算法過程兩個方面進行一定程度的改進，目的是在節(jié)點數(shù)和邊數(shù)較多的情況下，提高網(wǎng)絡(luò)模型的處理效率。以真實道路交通數(shù)據(jù)為基礎(chǔ)進行相關(guān)實驗，結(jié)果證明，改進后的Dijkstra算法可以有效減少節(jié)點的計算量，提高算法的運行效率。

[關(guān)鍵詞]Dijkstra算法；算法改進；路徑規(guī)劃

[中圖分類號]TP 31156[文獻標志碼]A[文章編號]10050310（2018）0200

6106

Abstract： Path planning is the core issue in emergency resource distribution. The shortest path algorithm plays a decisive role in the path planning process. The most classic and most representative path planning algorithm is the Dijkstra algorithm. Based on the traditional Dijkstra algorithm analysis， a certain degree of improvement has been made in storage structure and the algorithm process. The purpose is to improve the efficiency of the network model with more nodes and more edges. Experiments are carried out on the basis of real road traffic data and the results show that the improved Dijkstra algorithm can effectively reduce the calculation of nodes and improve the efficiency of the algorithm.

Keywords： Dijkstra algorithm； Algorithm improvement； Path planning

0引言

Dijkstra算法是解決路徑規(guī)劃問題的核心算法。路徑規(guī)劃是指在行駛前或者行駛過程中向駕駛員提供參考行駛路線的過程，是車輛定位與導(dǎo)航系統(tǒng)的基本功能之一。路徑規(guī)劃過程中有著不同的優(yōu)化標準，如最短距離、最少行駛時間及最大運載量[1]。但無論使用何種標準，路徑規(guī)劃最終都可以歸類為在特定道路網(wǎng)絡(luò)中以搜索總代價最小為目的的目標路徑問題，所以最短路徑問題正是網(wǎng)絡(luò)分析中最關(guān)鍵、最重要的問題[2]。

隨著信息技術(shù)的發(fā)展，最短路徑問題在交通、地理、物流、道路規(guī)劃及網(wǎng)絡(luò)布局等實際生活中日益凸顯出其重要性[3]。在解決最短路徑問題的算法中，比較流行且具代表性的算法就是Dijkstra算法及其改進算法[4]。本文將針對傳統(tǒng)的Dijkstra算法所面臨的多節(jié)點數(shù)和多邊數(shù)網(wǎng)絡(luò)模型的應(yīng)用局限性，主要討論Dijkstra算法的改進算法。

1經(jīng)典的Dijkstra算法

11Dijkstra算法的基本思想

Dijkstra算法是典型的單源點最短路徑算法，是由荷蘭計算機科學(xué)家E.W.Dijkstra在1959年提出的[5]。Dijkstra算法的主要特點是以起始點為中心，向與之直接相連的點層層擴展，每次以距離最小化為判定標準，直到擴展到終點得到最短距離。

在抽象為圖論的意義之下，用Dijkstra算法計算圖中的最短路徑時，需要指定起點s（即從頂點s開始計算）。另外需要加入兩個集合S和U的運算，S集合用來記錄已經(jīng)求出最短路徑的頂點以及起點與其他各頂點之間的暫時最短路徑，U集合用來記錄還未求出最短路徑的頂點以及起點與其他各頂點之間的距離。

初始時，S中只有起點s；U中包括除起點s之外的所有頂點，且U中各頂點的路徑是“起點s到該頂點的路徑”。從U中遍歷出路徑最短的頂點，并將該頂點加到S中；更新U中各頂點對應(yīng)的路徑。然后循環(huán)上述過程，直到遍歷完所有頂點，最終得到的路徑長度即為起點s到所有頂點的最短路徑長度。

12Dijkstra算法的操作步驟

1） 初始化：S集合中只含有起點s；U集合中含有除s之外的其他所有頂點，且各頂點距離標識為“起點s到該頂點的距離”，不直接相連標識為無窮大。即S{}=s，U{}=其他頂點，ds=0。源點標號為s，而其他點尚未處理。

2） 檢驗U中其他所有點到s的距離，并選出距離最小的一個點k，并將頂點k加入到集合S中，同時從集合U中刪除頂點k。即：

dsk=min[dsj]。（1）

3） 更新集合U中起點s到所有其他各頂點的距離。更新原因是由于前一步已經(jīng)確定了k是最短路徑中的頂點，而前一頂點經(jīng)過頂點k到達下一頂點的路徑長度比直接到達下一頂點的路徑長度小，這一可能性是存在的，那么就需要再次進行最短距離更新，以距離最小化為判定標準。即：

dsv =min[dsv，dsk+dkv]。（2）

4） 重復(fù)步驟2）和3），直到遍歷完所有頂點，那么最終S集合包含所有頂點，U集合為空。S集合中的距離即為源點s到各頂點的最短距離。

13Dijkstra算法應(yīng)用舉例

下面用具體實例闡述Dijkstra算法在路徑規(guī)劃中的應(yīng)用。如圖1所示，點與連線是對實際交通道路網(wǎng)絡(luò)拓撲部分結(jié)構(gòu)的模擬，其中A至F各點代表各交通十字路口，點與點之間的連線代表各條道路。利用Dijkstra算法，求出點A到F的最短路徑。

21最優(yōu)存儲結(jié)構(gòu)的選取

對于網(wǎng)絡(luò)數(shù)據(jù)的存儲方式，有兩種存儲結(jié)構(gòu)可以選?。亨徑泳仃嚭袜徑颖?。圖論中對于網(wǎng)絡(luò)數(shù)據(jù)的存儲采用的是鄰接矩陣的方法[7]。

將圖以鄰接矩陣的形式存儲時，可以用二維數(shù)組表示任意兩點之間的連接情況。當兩點為同一節(jié)點時，對應(yīng)的數(shù)組值為0，反之則不為0。當需要對兩點之間的權(quán)值進行操作時，比如道路的長度、資源的數(shù)量等，如果兩點是直接連接的，則對應(yīng)的矩陣值就是兩點之間的權(quán)值大小；如果兩點不直接相連，則對應(yīng)的矩陣值為無窮大。這種表示方法簡單、直接。矩陣以數(shù)組的方式表示時申請和釋放都比較靈活方便。但在網(wǎng)絡(luò)節(jié)點數(shù)較多的情況下，需要大量的存儲空間，尤其是在網(wǎng)絡(luò)比較稀疏的情況下，鄰接矩陣會存儲較多無窮大的非計算網(wǎng)絡(luò)節(jié)點，也會造成一定的空間浪費[8]。

將圖以鄰接表的形式存儲時，存儲空間大體相當于弧度表示法，靈活性比較強，并且存儲空間較小。但在進行相應(yīng)的節(jié)點操作時，程序的正確性不太容易把握，尤其在網(wǎng)絡(luò)節(jié)點數(shù)量龐大時，操作性較差。

實驗數(shù)據(jù)表明，在前期網(wǎng)絡(luò)節(jié)點較少時，將同一種算法分別采用鄰接表和鄰接矩陣兩種存儲方式，其執(zhí)行時間基本相同。隨著網(wǎng)絡(luò)節(jié)點數(shù)目的增多，鄰接表不適用于

節(jié)點數(shù)量多的劣勢明顯突出，實驗時間明顯增加；而鄰接矩陣并沒有明顯表現(xiàn)出其存儲空間浪費從而影響算法執(zhí)行效率的問題，實驗時間緩慢穩(wěn)定地增加。

在大規(guī)模交通疏散中，各應(yīng)急避難點以網(wǎng)絡(luò)節(jié)點的形式按照某種存儲方式存儲在網(wǎng)絡(luò)中。在應(yīng)急避難點較多的情況下，對比實驗結(jié)果數(shù)據(jù)，采用鄰接矩陣的存儲方式進行網(wǎng)絡(luò)節(jié)點的存儲，效果較好。

22算法效率的改進策略

在Dijkstra算法的實現(xiàn)過程中可以看出，其中最主要的一個核心步驟就是從未選定為最短距離的網(wǎng)絡(luò)節(jié)點中選擇一個當前集合中權(quán)值最小的點，即距離源點最近的點[9]。這是一個循環(huán)比較的過程，如果中間不采取任何比較篩選策略，未標記的點將被逐一循環(huán)比較，在大數(shù)據(jù)量的網(wǎng)絡(luò)節(jié)點的情況下，這無疑是制約計算速度的瓶頸。

221添加網(wǎng)絡(luò)節(jié)點的標記flag

采用布爾值類型的數(shù)組flag對算法過程中的節(jié)點做標記。如果網(wǎng)絡(luò)節(jié)點已經(jīng)選定為最短距離節(jié)點，則標記為true，否則標記為false。初始化時，將所有網(wǎng)絡(luò)節(jié)點的值都標記為false，算法過程中逐一選定修改，最終執(zhí)行完所有（節(jié)點數(shù)減1次）循環(huán)后，所有節(jié)點都被選定完畢，其對應(yīng)flag值都應(yīng)當標記為true。對未選定的節(jié)點進行權(quán)值最小篩選時，只要篩選flag值為false的節(jié)點即可。

222添加最小路徑變量min

采用整型變量min對未確定最短距離的網(wǎng)絡(luò)節(jié)點的值作標記，通過比較選出最小距離。初始化定義整型變量min為最大值，伴隨著數(shù)組的遍歷，min的值會越來越小。在判別時，必須滿足flag值為false并且min的值小于當前min，才會對該網(wǎng)絡(luò)節(jié)點重新賦值并記錄下當前節(jié)點的標記號，否則直接跳過。這種比較方法實現(xiàn)了每次搜索僅需一次循環(huán)便可找到未標記網(wǎng)絡(luò)節(jié)點的最小權(quán)值。

23基于真實交通道路數(shù)據(jù)的相關(guān)實驗

231實驗數(shù)據(jù)

實驗以北京市電子道路數(shù)據(jù)為基礎(chǔ)數(shù)據(jù)，數(shù)據(jù)保存在shapfile格式的文件中。通過解析文件內(nèi)容，讀取道路相關(guān)數(shù)據(jù)，包括道路ID、形狀、寬度、方向、名稱、起始節(jié)點ID、終止節(jié)點ID和長度等。電子道路數(shù)據(jù)總計87 855條，解析后按照ID依次排列于TXT文件中，解析結(jié)果如圖2所示。北京市道路交通電子地圖如圖3所示。

232實驗過程

以一條道路的起始節(jié)點作為整個實驗道路數(shù)據(jù)節(jié)點中的起始節(jié)點，再以這條道路的終止節(jié)點作為后一條或幾條道路的起始節(jié)點，通過層層擴展，建立真實道路的網(wǎng)絡(luò)拓撲結(jié)構(gòu)。

通過僅改變道路網(wǎng)絡(luò)拓撲的復(fù)雜度的方法，即只改變道路節(jié)點數(shù)量，將選出的道路節(jié)點按照阿拉伯數(shù)字順序依次編號，以當前道路節(jié)點到其他所有道路節(jié)點的最短距離為例，最后對Dijkstra算法運行時長進行比較，進行相關(guān)實驗。

首先當?shù)缆肪W(wǎng)絡(luò)拓撲圖中節(jié)點數(shù)量為50和100的情況下，實驗結(jié)果如圖4所示。左側(cè)是以鄰接表形式存儲數(shù)據(jù)的Dijkstra算法實驗結(jié)果，節(jié)點數(shù)為50時算法運行時長為63 ms，節(jié)點數(shù)為100時算法運行時長為80 ms；右側(cè)是以矩陣形式存儲數(shù)據(jù)的Dijkstra算法實驗結(jié)果，可以看出在節(jié)點數(shù)量為50和100的情況下，算法運行時長均與左側(cè)結(jié)果相同。

逐漸增加道路網(wǎng)絡(luò)拓撲中的節(jié)點數(shù)量，在節(jié)點數(shù)量為300、500和1 000時再次進行對比試驗，實驗結(jié)果如圖5所示。左側(cè)依然是以鄰接表形式存儲數(shù)據(jù)的Dijkstra算法實驗結(jié)果，右側(cè)是以矩陣形式存儲數(shù)據(jù)的Dijkstra算法實驗結(jié)果，可以發(fā)現(xiàn)在數(shù)據(jù)量逐漸增大的情況下，以鄰接表形式存儲數(shù)據(jù)明顯不如矩陣形式使得算法的運行效率高。

3Dijkstra算法在路徑規(guī)劃中的應(yīng)用

隨著城市規(guī)模的不斷擴大以及城市人口的高度密集，城市交通情況日益嚴峻，道路交通網(wǎng)絡(luò)日益脆弱。尤其是伴隨著很多交通事故和緊急事件的發(fā)生，大面積交通擁堵和交通癱瘓時常發(fā)生，因此應(yīng)急資源配送以及最短路徑尋優(yōu)工作迫在眉睫[10]。

專門針對大規(guī)模事故災(zāi)害的應(yīng)急資源儲備點一般分布在整個城區(qū)，仿真數(shù)據(jù)如圖6所示，以北京市交通電子道路地圖為例，顯示GIS系統(tǒng)中道路及應(yīng)急資源儲備點分布情況，其中應(yīng)急資源儲備點用紅色元素標識。一旦城區(qū)某處或多處發(fā)生大規(guī)模災(zāi)害事故，在應(yīng)急資源配送過程中，往往會面臨從多個儲備點向一個事故點的資源配送問題，如何才能找到距離最近的應(yīng)急資源儲備點顯得格外重要。

Dijkstra算法在GIS系統(tǒng)中路徑規(guī)劃方面的應(yīng)用很好地解決了這一問題。城市災(zāi)害事故發(fā)生時，

首先確立應(yīng)急資源配送目的節(jié)點的坐標位置（X，Y），

然后通過目的節(jié)點坐標的確立，運用Dijkstra算法進行

路徑規(guī)劃，得到距離當前災(zāi)害事故發(fā)生點最近的一個或幾個應(yīng)急資源儲備節(jié)點的坐標。如圖7所示，確定距離災(zāi)害事故發(fā)生節(jié)點最近的3個應(yīng)急資源儲備節(jié)點。

4結(jié)束語

本文在傳統(tǒng)Dijkstra算法的基礎(chǔ)上，對該算法在存儲結(jié)構(gòu)和算法邏輯過程兩個方面進行了改進。通過以網(wǎng)絡(luò)節(jié)點數(shù)據(jù)量為自變量，算法的執(zhí)行時間為因變量的相關(guān)編程實驗，結(jié)果證明改進后的Dijkstra算法可以有效減少節(jié)點的計算量，執(zhí)行效率相比之前有了明顯的提高，在路徑規(guī)劃方面尤其是在應(yīng)急資源配送的應(yīng)用中有著很好的前景。基于Dijkstra算法的最短路徑算法在物流管理、交通疏散等其他背景的應(yīng)用中效果依然顯著，這也是本文今后的研究方向。

[參考文獻]

[1]蘇永云，晏克非，黃翔，等.車輛導(dǎo)航系統(tǒng)的動態(tài)最優(yōu)路徑搜索方法研究[J].系統(tǒng)工程，2000， 18 （4）：32-37.

[2]樂陽， 龔健雅. Dijkstra最短路徑算法的一種高效率實現(xiàn)[J]. 武漢測繪科技大學(xué)學(xué)報， 1999， 24（3）： 209-212.

[3]彭定旭， 冀肖榆. Dijkstra算法的java實現(xiàn)方式及優(yōu)化[J]. 黑龍江科技信息， 2017（4）： 166-167.

[4]龔杰輝，白玲，高健美. 最短路徑算法的改進及其實現(xiàn)方法[J]. 解放軍測繪學(xué)院學(xué)報， 1998，15（2）：121-124.

[5]段汝東， 侯至群， 朱大明. 基于Java的Dijkstra最短路徑算法實現(xiàn)[J].價值工程， 2016， 35（21）： 208-210.

[6]李擎，宋頂立，張雙江，等.兩種改進的最優(yōu)路徑規(guī)劃算法[J].北京科技大學(xué)學(xué)報， 2005， 27 （3）：367-370.

[7]孟慶偉， 張冬姣. 基于Dijkstra最短路徑算法的優(yōu)化及應(yīng)用研究[J]. 電子商務(wù)， 2014（12）： 60-61.

[8]白洪濤， 孫吉貴， 焦洋，等. 網(wǎng)絡(luò)優(yōu)化算法的實現(xiàn)與比較[J]. 吉林大學(xué)學(xué)報（信息科學(xué)版）， 2002， 20（2）： 59-69.

[9]樂陽. 網(wǎng)絡(luò)分析模型在GIS中的實現(xiàn)與應(yīng)用[D]. 武漢：武漢測繪科技大學(xué)， 1999.

[10]張鈺. 城市交通緊急疏散管理方法及應(yīng)用研究[D]. 武漢：武漢理工大學(xué)， 2006.

（責任編輯白麗媛）