管理運(yùn)籌學(xué)中最短路徑問題Dijkstra算法改進(jìn)研究

陸毅 崔玉樸 汪坤 姚學(xué)勤

摘 ?要：Dijkstra算法是求解運(yùn)籌學(xué)最短路問題的重要方法之一。文章在分析傳統(tǒng)Dijkstra算法思想的基礎(chǔ)上尋求其優(yōu)化途徑，發(fā)現(xiàn)可以使用堆結(jié)構(gòu)來優(yōu)化傳統(tǒng)算法在查找最小值時(shí)重復(fù)查找標(biāo)記的遍歷過程。經(jīng)理論分析與具體實(shí)驗(yàn)測(cè)試，改進(jìn)后的算法在時(shí)間效率方面明顯優(yōu)于傳統(tǒng)算法，提高了該算法的效率和性能，具有較好的適用性。

關(guān)鍵詞：最短路徑;Dijkstra;堆;運(yùn)籌學(xué)

中圖分類號(hào)：TP301.6 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2096-4706（2021）13-0084-03

The Reaserch on Improvement of Dijkstra Algorithm for Shortest Path Problem in Management Operations Reaserch

LU Yi， CUI Yupu， WANG Kun， YAO Xueqin

（Department of ?Management，Wanjiang College of Anhui Normal University， Wuhu ?241008， China）

Abstract： Dijkstra algorithm is one of the important methods to solve the shortest path problem in operational research. Based on the analysis of the idea of the traditional Dijkstra algorithm， this paper seeks it’s optimization approach， and finds that the heap structure can be used to optimize the traversal process of the traditional algorithm to repeatedly find the tag when looking for the minimum value. Through theoretical analysis and specific experimental tests， the improved algorithm is significantly better than the traditional algorithm in time efficiency， improves the efficiency and performance of the algorithm， and has good applicability.

Keywords： shortest path; Dijkstra; heap; operations research

0 ?引 ?言

最短路徑問題是運(yùn)籌學(xué)網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一，在交通運(yùn)輸、城市規(guī)劃、物流運(yùn)輸、電子導(dǎo)航等方面都發(fā)揮了重要的作用。在實(shí)際運(yùn)用中，如碼頭集裝箱調(diào)度、物流運(yùn)輸線路、旅游路徑選擇等都可以使用這個(gè)模型。在求解無負(fù)權(quán)網(wǎng)絡(luò)最短路徑問題時(shí)，目前公認(rèn)的最好的求解方法是Dijkstra算法，至今仍在廣泛運(yùn)用。近年來隨著信息數(shù)據(jù)的爆發(fā)，大規(guī)模數(shù)據(jù)網(wǎng)絡(luò)最短路徑計(jì)算的需求大大增加。如導(dǎo)航系統(tǒng)、救援系統(tǒng)都需要在盡可能短的時(shí)間內(nèi)得出合適的路徑。這就要求最短路徑算法要有更高的效率與性能。

堆是一類數(shù)據(jù)結(jié)構(gòu)，是維護(hù)數(shù)據(jù)的一個(gè)集合。在排序的問題中，可以快速對(duì)數(shù)據(jù)進(jìn)行排序，時(shí)間復(fù)雜度為O（logn），并可以以O(shè)（1）的時(shí)間復(fù)雜度獲取最小值，時(shí)間效率較高。使用堆結(jié)構(gòu)來優(yōu)化傳統(tǒng)算法為獲取最小值時(shí)重復(fù)查找遍歷的過程可以減少此過程的運(yùn)算次數(shù)，降低算法的時(shí)間復(fù)雜度。

在傳統(tǒng)Dijkstra算法中，設(shè)具有n個(gè)頂點(diǎn)與m條邊無負(fù)權(quán)回路的有向圖G，算法的時(shí)間復(fù)雜度為0（n2），當(dāng)n的規(guī)模較大時(shí)，算法的時(shí)間效率較低，仍具有較大的提升空間。

1 ?傳統(tǒng)Dijkstra算法思想

Dijkstra算法適用于求解無負(fù)權(quán)回路網(wǎng)絡(luò)中單源最短路的最短路徑問題，用于計(jì)算網(wǎng)絡(luò)圖中某個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑代價(jià)。下面以一個(gè)具體例子來描述傳統(tǒng)Dijkstra算法的實(shí)現(xiàn)過程。給定一個(gè)具有n個(gè)頂點(diǎn)m條邊所有邊權(quán)w均為正值的有向圖G。求出開始節(jié)點(diǎn)（1號(hào)節(jié)點(diǎn)）到n號(hào)節(jié)點(diǎn)的最短距離，若開始節(jié)點(diǎn)到n號(hào)節(jié)點(diǎn)無通路，輸出-1。使用二維數(shù)組g[N][N]模擬鄰接矩陣來存儲(chǔ)具有n個(gè)節(jié)點(diǎn)的有向圖，使用一維數(shù)組dist[N]來存儲(chǔ)1號(hào)節(jié)點(diǎn)到i號(hào)節(jié)點(diǎn)的最短距離。設(shè)集合S為當(dāng)前已經(jīng)確定最短路徑的節(jié)點(diǎn)，并用布爾數(shù)組st[N]表示集合S。N大于頂點(diǎn)數(shù)n。下面是具體的步驟：

（1）對(duì)dist數(shù)組進(jìn)行初始化。將1號(hào)節(jié)點(diǎn)的距離初始化為0，其余各節(jié)點(diǎn)距1號(hào)節(jié)點(diǎn)的距離初始化為無窮大或一個(gè)較大的數(shù)。dist[1]=0，dist[i]=Inf。

（2）找出未確定最短路的節(jié)點(diǎn)t并將其加入集合S中。

（3）使用節(jié)點(diǎn)t到1號(hào)節(jié)點(diǎn)的距離更新其他節(jié)點(diǎn)到1號(hào)節(jié)點(diǎn)的最短距離。若i節(jié)點(diǎn)直接到1號(hào)節(jié)點(diǎn)的距離大于節(jié)點(diǎn)i經(jīng)過節(jié)點(diǎn)t到1號(hào)節(jié)點(diǎn)的距離，則用節(jié)點(diǎn)t更新到1號(hào)節(jié)點(diǎn)的距離，即dist[i]>dist[t]+g[t][i]，則dist[i] = dist[t]+g[t][i]。

（4）重復(fù)步驟2、步驟3的操作，直到S包含所有節(jié)點(diǎn)，算法結(jié)束，輸出結(jié)果。下面給出傳統(tǒng)Dijkstra算法函數(shù)的C++代碼實(shí)現(xiàn)：

int Dijkstra（） ?{

memset（dist， 0x3f， sizeof dist）;

dist[1] = 0;

for （int i = 0; i < n - 1; i++） ?{

int t = -1;

for （int j = 1; j <= n; j++）

if （！st[j] && （t == -1 || dist[t] > dist[j]）） ?t = j;

for （int j = 1; j <= n; j++）

dist[j] = min（dist[j]， dist[t] + g[t][j]）;

st[t] = true; ?}

if （dist[n] == 0x3f3f3f3f） ?return -1;

return dist[n]; ?}

在上述算法中，關(guān)鍵的步驟2需要找出不在集合S中的與1號(hào)節(jié)點(diǎn)距離最近的節(jié)點(diǎn)t。當(dāng)邊權(quán)值w存放在數(shù)組、鏈表等線性結(jié)構(gòu)時(shí)，數(shù)據(jù)在結(jié)構(gòu)中的存儲(chǔ)順序是亂序的，為了找出最小節(jié)點(diǎn)t，需要遍歷所有節(jié)點(diǎn)。該步驟的時(shí)間復(fù)雜度為O（n2），進(jìn)行了大量的循環(huán)計(jì)算，當(dāng)n的規(guī)模較大時(shí)，這無疑是一個(gè)制約算法運(yùn)算速度的瓶頸。步驟3需要對(duì)圖的m條邊進(jìn)行判斷，其時(shí)間復(fù)雜度為O（m）。圖中共有n個(gè)節(jié)點(diǎn)，將n個(gè)節(jié)點(diǎn)加入集合S中的時(shí)間復(fù)雜度為O（n）。因此傳統(tǒng)Dijkstra算法的時(shí)間復(fù)雜度為O（n2）。當(dāng)n大于10 000量級(jí)時(shí)，普通計(jì)算機(jī)并不能在1 s之內(nèi)得出正確結(jié)果。這樣高的時(shí)間復(fù)雜度并不能滿足大規(guī)模數(shù)據(jù)網(wǎng)絡(luò)及時(shí)性的需求，因此對(duì)傳統(tǒng)算法進(jìn)行優(yōu)化是有必要的。

2 ?堆優(yōu)化Dijkstra算法

傳統(tǒng)Dijkstra算法固然經(jīng)典，但當(dāng)n的規(guī)模較大時(shí)，算法效率受限，不能滿足大規(guī)模數(shù)據(jù)網(wǎng)絡(luò)最短路徑實(shí)時(shí)計(jì)算的需求，利用堆結(jié)構(gòu)思想可實(shí)現(xiàn)有效改進(jìn)。

2.1 ?堆（小根堆）

堆是一個(gè)維護(hù)數(shù)據(jù)的集合，若將集合T中所有的元素按照完全二叉樹的順序儲(chǔ)存在一個(gè)一維數(shù)組中便構(gòu)建出了堆。其本質(zhì)是一棵完全二叉樹，又根據(jù)堆頂元素為所有元素的最大值或最小值分為大根堆與小根堆。其中小根堆具有以下性質(zhì)：其父節(jié)點(diǎn)的值小于等于子節(jié)點(diǎn)的值，堆頂?shù)闹凳嵌阎凶钚〉?。這樣的性質(zhì)完全可以滿足傳統(tǒng)Dijkstra算法查找最小節(jié)點(diǎn)t的需求，優(yōu)化傳統(tǒng)算法中遍歷的過程。因此可以選擇采用小根堆結(jié)構(gòu)來優(yōu)化傳統(tǒng)Dijkstra算法。用一維數(shù)組heap[N]來存儲(chǔ)堆元素，設(shè)根節(jié)點(diǎn)的下標(biāo)為x，則根節(jié)點(diǎn)左子節(jié)點(diǎn)的下標(biāo)為2x，右子節(jié)點(diǎn)的下標(biāo)為2·x+1。heap[1]為堆頂。

2.2 ?堆在Dijkstra算法中的應(yīng)用

堆有兩種基本操作，up操作與down操作。當(dāng)某個(gè)節(jié)點(diǎn)的值大于其子節(jié)點(diǎn)的值或小于其父節(jié)點(diǎn)的值時(shí)，便需要up操作或down操作來進(jìn)行調(diào)整，以此來維持堆的性質(zhì)。下面簡(jiǎn)要介紹兩種操作：

up操作：比較子節(jié)點(diǎn)與父節(jié)點(diǎn)值的大小，若子節(jié)點(diǎn)的值小于父節(jié)點(diǎn)，則對(duì)兩個(gè)節(jié)點(diǎn)的值進(jìn)行一次交換，直到heap[x]找到合適的位置。即若heap[2·x]（或heap[2·x+1]）

down操作：比較父節(jié)點(diǎn)與左右子節(jié)點(diǎn)值的大小，取元素值較小的路徑。若父節(jié)點(diǎn)的值大于子節(jié)點(diǎn)，則對(duì)兩個(gè)節(jié)點(diǎn)的值進(jìn)行一次交換，直到heap[x]找到合適的位置。即若heap[x]> min（heap[2·x]，heap[2·x+1]），swap（heap[x]，min（heap[2·x]，heap[2·x+1]）。

在Dijkstra算法中，除了這兩種基礎(chǔ)操作外，還需要算法支持修改節(jié)點(diǎn)元素值、插入節(jié)點(diǎn)和刪除節(jié)點(diǎn)等操作：

修改節(jié)點(diǎn)元素值：直接修改該節(jié)點(diǎn)元素值，再根據(jù)需求進(jìn)行up操作與down操作將其調(diào)整到合適的位置。

插入節(jié)點(diǎn)：增加一個(gè)節(jié)點(diǎn)位，將該節(jié)點(diǎn)放入堆中最后的一個(gè)位置，再進(jìn)行up操作將其調(diào)整到合適的位置。

刪除節(jié)點(diǎn)：用堆中最后一個(gè)元素替代該節(jié)點(diǎn)，刪除最后一個(gè)元素的節(jié)點(diǎn)位，再根據(jù)需求進(jìn)行up操作與down操作將其調(diào)整到合適的位置。

這些操作，均可以使用up操作和down操作來完成實(shí)現(xiàn)。

根據(jù)堆的性質(zhì)，無論是父節(jié)點(diǎn)元素值大于左右子節(jié)點(diǎn)元素值還是左右子節(jié)點(diǎn)元素值小于父節(jié)點(diǎn)元素值，up操作與down操作只可能運(yùn)行其中一個(gè)。為了降低代碼的復(fù)雜度，可以省略判斷元素值部分的代碼使代碼更具有簡(jiǎn)明性，增加程序的魯棒性。x為當(dāng)前需要操作的節(jié)點(diǎn)下標(biāo)，size為當(dāng)前堆的大小，m為賦給待修改節(jié)點(diǎn)的元素值。

修改節(jié)點(diǎn)元素值：heap[x] = m; up（x）; down（x）;

插入節(jié)點(diǎn)：heap[++size] = x; up（size）;

刪除節(jié)點(diǎn)：heap[x] = heap[size]; size--; up（x）; down（x）;

2.3 ?優(yōu)先隊(duì)列（Priority Queue）實(shí)現(xiàn)堆優(yōu)化Dijkstra算法

在具體代碼實(shí)現(xiàn)中，手寫堆結(jié)構(gòu)較為復(fù)雜。在C++語(yǔ)言的STL庫(kù)中封裝了priority_queue結(jié)構(gòu)，為了減少代碼復(fù)雜度，選擇使用優(yōu)先隊(duì)列來完善算法的具體代碼。在優(yōu)先隊(duì)列中，元素會(huì)被賦予不同的優(yōu)先級(jí)，當(dāng)訪問元素時(shí)，具有最高優(yōu)先級(jí)的元素優(yōu)先出隊(duì)。給予隊(duì)列元素值最小為優(yōu)先級(jí)時(shí)，隊(duì)頭則為所需求的元素最小值。在數(shù)據(jù)量較大時(shí)，如果采用鄰接矩陣來存儲(chǔ)網(wǎng)絡(luò)圖，空間復(fù)雜度較高，存儲(chǔ)空間占用量較大，使用一維數(shù)組模擬鄰接表存儲(chǔ)網(wǎng)絡(luò)圖，可降低算法的空間復(fù)雜度，減少計(jì)算機(jī)存儲(chǔ)空間的使用。h數(shù)組、e數(shù)組與ne數(shù)組構(gòu)成鄰接表來存儲(chǔ)圖，w數(shù)組存儲(chǔ)邊權(quán)值。改進(jìn)后的Dijkstra函數(shù)C++代碼為：

typedef pair<int， int> PII;

int Dijkstra（） ?{

memset（dist， 0x3f， sizeof dist）;

dist[1] = 0;

priority_queue<PII， vector<PII>， greater<PII> > heap;

heap.push （{0， 1}）;

while （heap.size（）） {

PII t = heap.top（）;

heap.pop（）;

int dis = t.first， int v = t.second;

if （st[v]） ?continue;

st[v] = true;

for （int i = h[v]; i ！= -1; i = ne[i]） {

int j = e[i];

if （dist[j] > dist[v] + w[i]） {

dist[j] = dist[v] + w[i];

heap.push（{dist[j]， j}）; ?}}}

if （dist[n] == 0x3f3f3f3f） return -1;

return dist[n]; ?}

2.4 ?堆優(yōu)化Dijkstra算法時(shí)間復(fù)雜度分析

在傳統(tǒng)Dijkstra算法中，遍歷查找最小值為算法瓶頸，時(shí)間復(fù)雜度為O（n2）。在優(yōu)化后的算法中，查找最小值這一過程被優(yōu)先隊(duì)列結(jié)構(gòu)代替。優(yōu)先隊(duì)列又為堆結(jié)構(gòu)實(shí)現(xiàn)。獲取最小值，即用堆中最后一個(gè)元素代替堆頂元素，再進(jìn)行down操作進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為O（logn）。共有n個(gè)節(jié)點(diǎn)，總時(shí)間復(fù)雜度為O（nlogn）。對(duì)m條邊進(jìn)行判斷，其時(shí)間復(fù)雜度為O（m）。因此優(yōu)化后的Dijkstra算法的時(shí)間復(fù)雜度為O（nlogn）。相較于傳統(tǒng)Dijkstra算法O（n2）的時(shí)間復(fù)雜度有了較大的進(jìn)步。即使n為1 000 000的量級(jí)時(shí)，也可在1 s內(nèi)得出結(jié)果。

3 ?兩種算法大規(guī)模數(shù)據(jù)運(yùn)行測(cè)試

為了檢驗(yàn)改進(jìn)后的Dijkstra算法，對(duì)算法采用較大規(guī)模的數(shù)據(jù)量進(jìn)行測(cè)試。進(jìn)而比較傳統(tǒng)Dijkstra算法與堆優(yōu)化Dijkstra算法在實(shí)際運(yùn)行中的時(shí)間效率。分別取頂點(diǎn)數(shù)n為100，1 000，5 000，10 000，20 000，100 000，1 000 000來進(jìn)行測(cè)試。接下來的實(shí)驗(yàn)中，將統(tǒng)一使用這些數(shù)據(jù)進(jìn)行測(cè)試，以此來對(duì)比兩種算法在時(shí)間效率方面的優(yōu)劣。使用C++語(yǔ)言中<ctime>標(biāo)準(zhǔn)庫(kù)中的clock（）函數(shù)來進(jìn)行計(jì)時(shí)，測(cè)試兩種算法中Dijkstra函數(shù)的運(yùn)行時(shí)間。所用計(jì)算機(jī)為惠普筆記本電腦，測(cè)試環(huán)境為Dev-C++ IDE 5.4.0，操作系統(tǒng)為Win 10家庭中文版，CPU為Intel（R） Core（TM） i5-8300H CPU @ 2.30 GHz，內(nèi)存為16 GB DDR4。其測(cè)試結(jié)果如表1所示。

由表1的試驗(yàn)測(cè)試結(jié)果來看，隨著n的規(guī)模不斷增大，堆優(yōu)化Dijkstra算法的運(yùn)行時(shí)間愈發(fā)短暫，遠(yuǎn)優(yōu)于傳統(tǒng)算法。傳統(tǒng)算法當(dāng)n大于10 000時(shí)，程序的運(yùn)行時(shí)間急劇增加。n為20 000時(shí)就需要幾秒鐘的時(shí)間來進(jìn)行運(yùn)算，而堆優(yōu)化Dijkstra算法仍只需要幾毫秒便可以得出結(jié)果，時(shí)間效率遠(yuǎn)優(yōu)于傳統(tǒng)算法。這樣的時(shí)間效率完全可以滿足較大數(shù)據(jù)規(guī)模網(wǎng)絡(luò)圖計(jì)算最短路徑的問題，可以應(yīng)用于對(duì)及時(shí)性要求較高的導(dǎo)航、救援等系統(tǒng)。這也說明了使用堆結(jié)構(gòu)來優(yōu)化傳統(tǒng)Dijkstra算法是完全可行的。

4 ?結(jié) ?論

本文在傳統(tǒng)算法的基礎(chǔ)上，使用堆結(jié)構(gòu)來優(yōu)化傳統(tǒng)算法查找最小值時(shí)重復(fù)查找標(biāo)記的遍歷過程，并具體實(shí)現(xiàn)了堆優(yōu)化Dijkstra算法。相對(duì)于傳統(tǒng)算法使用遍歷算法來查找最短路徑的節(jié)點(diǎn)，使用堆結(jié)構(gòu)只需要比較相鄰節(jié)點(diǎn)的值，并可直接獲取最小值，減少了程序運(yùn)行時(shí)的計(jì)算次數(shù)，提高了算法的時(shí)間效率。使用了大規(guī)模數(shù)據(jù)進(jìn)行測(cè)試，研究比較了傳統(tǒng)Dijkstra算法與堆優(yōu)化Dijkstra算法的時(shí)間復(fù)雜度與運(yùn)行時(shí)間。將傳統(tǒng)Dijkstra算法O（n2）階的時(shí)間復(fù)雜度降低至O（nlogn）階。實(shí)驗(yàn)結(jié)果顯示，堆優(yōu)化Dijkstra算法在時(shí)間效率方面遠(yuǎn)優(yōu)于傳統(tǒng)算法，大大提高了傳統(tǒng)算法的效率與性能。

參考文獻(xiàn)：

[1] 張翰林，關(guān)愛薇，傅珂，等.Dijkstra最短路徑算法的堆優(yōu)化實(shí)驗(yàn)研究 [J].軟件，2017，38（5）：15-21.

[2] 王志和，凌云.Dijkstra最短路徑算法的優(yōu)化及其實(shí)現(xiàn) [J].微計(jì)算機(jī)信息，2007，（33）：275-277.

[3] 邱慧，黃解宇，黃麗丹.管理運(yùn)籌學(xué)中最短路問題的兩種算法研究 [J].運(yùn)城學(xué)院學(xué)報(bào)，2014，32（2）：89-91.

[4] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） [M].北京：清華大學(xué)出版社，2002.

[5] 李健.基于Dijkstra最短路徑算法的優(yōu)化研究 [J].渭南師范學(xué)院學(xué)報(bào)，2009，24（5）：61-64.

[6] 韓偉一.基于固定序的Bellman-Ford算法的改進(jìn) [J].運(yùn)籌與管理，2015，24（4）：111-115.

[7] DIJKSTRA E W. A note on two problems in connexion with graphs [J].Numerical Mathematics，1959，1（1）：269-271.

[8] 胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程 [M].北京：清華大學(xué)出版社，1998.

[9] 曲大鵬，侯振桓，宣偉宏，等.最小生成樹相關(guān)算法在計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽中的研究 [J].遼寧大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，47（2）：118-123.

作者簡(jiǎn)介：陸毅（2000—），男，漢族，安徽蚌埠人，本科在讀，研究方向：運(yùn)籌學(xué)。