管理運籌學中最短路徑問題Dijkstra算法改進研究

陸毅 崔玉樸 汪坤 姚學勤

摘 ?要：Dijkstra算法是求解運籌學最短路問題的重要方法之一。文章在分析傳統Dijkstra算法思想的基礎上尋求其優化途徑，發現可以使用堆結構來優化傳統算法在查找最小值時重復查找標記的遍歷過程。經理論分析與具體實驗測試，改進后的算法在時間效率方面明顯優于傳統算法，提高了該算法的效率和性能，具有較好的適用性。

關鍵詞：最短路徑;Dijkstra;堆;運籌學

中圖分類號：TP301.6 ? ? 文獻標識碼：A文章編號：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 ?引 ?言

最短路徑問題是運籌學網絡理論中應用最廣泛的問題之一，在交通運輸、城市規劃、物流運輸、電子導航等方面都發揮了重要的作用。在實際運用中，如碼頭集裝箱調度、物流運輸線路、旅游路徑選擇等都可以使用這個模型。在求解無負權網絡最短路徑問題時，目前公認的最好的求解方法是Dijkstra算法，至今仍在廣泛運用。近年來隨著信息數據的爆發，大規模數據網絡最短路徑計算的需求大大增加。如導航系統、救援系統都需要在盡可能短的時間內得出合適的路徑。這就要求最短路徑算法要有更高的效率與性能。

堆是一類數據結構，是維護數據的一個集合。在排序的問題中，可以快速對數據進行排序，時間復雜度為O（logn），并可以以O（1）的時間復雜度獲取最小值，時間效率較高。使用堆結構來優化傳統算法為獲取最小值時重復查找遍歷的過程可以減少此過程的運算次數，降低算法的時間復雜度。

在傳統Dijkstra算法中，設具有n個頂點與m條邊無負權回路的有向圖G，算法的時間復雜度為0（n2），當n的規模較大時，算法的時間效率較低，仍具有較大的提升空間。

1 ?傳統Dijkstra算法思想

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

（1）對dist數組進行初始化。將1號節點的距離初始化為0，其余各節點距1號節點的距離初始化為無窮大或一個較大的數。dist[1]=0，dist[i]=Inf。

（2）找出未確定最短路的節點t并將其加入集合S中。

（3）使用節點t到1號節點的距離更新其他節點到1號節點的最短距離。若i節點直接到1號節點的距離大于節點i經過節點t到1號節點的距離，則用節點t更新到1號節點的距離，即dist[i]>dist[t]+g[t][i]，則dist[i] = dist[t]+g[t][i]。

（4）重復步驟2、步驟3的操作，直到S包含所有節點，算法結束，輸出結果。下面給出傳統Dijkstra算法函數的C++代碼實現：

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]; ?}

在上述算法中，關鍵的步驟2需要找出不在集合S中的與1號節點距離最近的節點t。當邊權值w存放在數組、鏈表等線性結構時，數據在結構中的存儲順序是亂序的，為了找出最小節點t，需要遍歷所有節點。該步驟的時間復雜度為O（n2），進行了大量的循環計算，當n的規模較大時，這無疑是一個制約算法運算速度的瓶頸。步驟3需要對圖的m條邊進行判斷，其時間復雜度為O（m）。圖中共有n個節點，將n個節點加入集合S中的時間復雜度為O（n）。因此傳統Dijkstra算法的時間復雜度為O（n2）。當n大于10 000量級時，普通計算機并不能在1 s之內得出正確結果。這樣高的時間復雜度并不能滿足大規模數據網絡及時性的需求，因此對傳統算法進行優化是有必要的。

2 ?堆優化Dijkstra算法

傳統Dijkstra算法固然經典，但當n的規模較大時，算法效率受限，不能滿足大規模數據網絡最短路徑實時計算的需求，利用堆結構思想可實現有效改進。

2.1 ?堆（小根堆）

堆是一個維護數據的集合，若將集合T中所有的元素按照完全二叉樹的順序儲存在一個一維數組中便構建出了堆。其本質是一棵完全二叉樹，又根據堆頂元素為所有元素的最大值或最小值分為大根堆與小根堆。其中小根堆具有以下性質：其父節點的值小于等于子節點的值，堆頂的值是堆中最小的。這樣的性質完全可以滿足傳統Dijkstra算法查找最小節點t的需求，優化傳統算法中遍歷的過程。因此可以選擇采用小根堆結構來優化傳統Dijkstra算法。用一維數組heap[N]來存儲堆元素，設根節點的下標為x，則根節點左子節點的下標為2x，右子節點的下標為2·x+1。heap[1]為堆頂。

2.2 ?堆在Dijkstra算法中的應用

堆有兩種基本操作，up操作與down操作。當某個節點的值大于其子節點的值或小于其父節點的值時，便需要up操作或down操作來進行調整，以此來維持堆的性質。下面簡要介紹兩種操作：

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

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

在Dijkstra算法中，除了這兩種基礎操作外，還需要算法支持修改節點元素值、插入節點和刪除節點等操作：

修改節點元素值：直接修改該節點元素值，再根據需求進行up操作與down操作將其調整到合適的位置。

插入節點：增加一個節點位，將該節點放入堆中最后的一個位置，再進行up操作將其調整到合適的位置。

刪除節點：用堆中最后一個元素替代該節點，刪除最后一個元素的節點位，再根據需求進行up操作與down操作將其調整到合適的位置。

這些操作，均可以使用up操作和down操作來完成實現。

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

修改節點元素值：heap[x] = m; up（x）; down（x）;

插入節點：heap[++size] = x; up（size）;

刪除節點：heap[x] = heap[size]; size--; up（x）; down（x）;

2.3 ?優先隊列（Priority Queue）實現堆優化Dijkstra算法

在具體代碼實現中，手寫堆結構較為復雜。在C++語言的STL庫中封裝了priority_queue結構，為了減少代碼復雜度，選擇使用優先隊列來完善算法的具體代碼。在優先隊列中，元素會被賦予不同的優先級，當訪問元素時，具有最高優先級的元素優先出隊。給予隊列元素值最小為優先級時，隊頭則為所需求的元素最小值。在數據量較大時，如果采用鄰接矩陣來存儲網絡圖，空間復雜度較高，存儲空間占用量較大，使用一維數組模擬鄰接表存儲網絡圖，可降低算法的空間復雜度，減少計算機存儲空間的使用。h數組、e數組與ne數組構成鄰接表來存儲圖，w數組存儲邊權值。改進后的Dijkstra函數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 ?堆優化Dijkstra算法時間復雜度分析

在傳統Dijkstra算法中，遍歷查找最小值為算法瓶頸，時間復雜度為O（n2）。在優化后的算法中，查找最小值這一過程被優先隊列結構代替。優先隊列又為堆結構實現。獲取最小值，即用堆中最后一個元素代替堆頂元素，再進行down操作進行調整，其時間復雜度為O（logn）。共有n個節點，總時間復雜度為O（nlogn）。對m條邊進行判斷，其時間復雜度為O（m）。因此優化后的Dijkstra算法的時間復雜度為O（nlogn）。相較于傳統Dijkstra算法O（n2）的時間復雜度有了較大的進步。即使n為1 000 000的量級時，也可在1 s內得出結果。

3 ?兩種算法大規模數據運行測試

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

由表1的試驗測試結果來看，隨著n的規模不斷增大，堆優化Dijkstra算法的運行時間愈發短暫，遠優于傳統算法。傳統算法當n大于10 000時，程序的運行時間急劇增加。n為20 000時就需要幾秒鐘的時間來進行運算，而堆優化Dijkstra算法仍只需要幾毫秒便可以得出結果，時間效率遠優于傳統算法。這樣的時間效率完全可以滿足較大數據規模網絡圖計算最短路徑的問題，可以應用于對及時性要求較高的導航、救援等系統。這也說明了使用堆結構來優化傳統Dijkstra算法是完全可行的。

4 ?結 ?論

本文在傳統算法的基礎上，使用堆結構來優化傳統算法查找最小值時重復查找標記的遍歷過程，并具體實現了堆優化Dijkstra算法。相對于傳統算法使用遍歷算法來查找最短路徑的節點，使用堆結構只需要比較相鄰節點的值，并可直接獲取最小值，減少了程序運行時的計算次數，提高了算法的時間效率。使用了大規模數據進行測試，研究比較了傳統Dijkstra算法與堆優化Dijkstra算法的時間復雜度與運行時間。將傳統Dijkstra算法O（n2）階的時間復雜度降低至O（nlogn）階。實驗結果顯示，堆優化Dijkstra算法在時間效率方面遠優于傳統算法，大大提高了傳統算法的效率與性能。

參考文獻：

[1] 張翰林，關愛薇，傅珂，等.Dijkstra最短路徑算法的堆優化實驗研究 [J].軟件，2017，38（5）：15-21.

[2] 王志和，凌云.Dijkstra最短路徑算法的優化及其實現 [J].微計算機信息，2007，（33）：275-277.

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

[4] 嚴蔚敏，吳偉民.數據結構（C語言版） [M].北京：清華大學出版社，2002.

[5] 李健.基于Dijkstra最短路徑算法的優化研究 [J].渭南師范學院學報，2009，24（5）：61-64.

[6] 韓偉一.基于固定序的Bellman-Ford算法的改進 [J].運籌與管理，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] 胡運權，郭耀煌.運籌學教程 [M].北京：清華大學出版社，1998.

[9] 曲大鵬，侯振桓，宣偉宏，等.最小生成樹相關算法在計算機程序設計競賽中的研究 [J].遼寧大學學報（自然科學版），2020，47（2）：118-123.

作者簡介：陸毅（2000—），男，漢族，安徽蚌埠人，本科在讀，研究方向：運籌學。