一種基于改進Dijkstra的物流網絡路徑優化算法分析

袁 彬，劉建勝，錢 丹，羅大海

YUAN Bin, LIU Jian-sheng, QIAN Dan, LUO Da-hai

（南昌大學 機電工程學院，南昌 330031）

0 引言

隨著現代制造業競爭加劇，物流在整個制造業供應鏈管理中的作用日益凸顯重要。企業管理者開始從戰略高度關注制造物流管理，旨在通過控制物流成本來降低產品總成本，提高產品競爭力。研究人員也紛紛對制造物流網絡的管理與規劃問題開展研究，如文獻[1]研究應用改進蟻群算法解決物流配送問題。路徑優化是物流網絡規劃的關鍵問題，目前，迪杰斯特拉（Dijkstra）算法是目前公認的較好的路徑優化算法之一。但是由于Dijkstra 算法頻繁遍歷所有的臨時標記結點,明顯降低了算法的運行速度和效率，特別是隨著網絡節點規模的增大，將導致算法運行時間長，難以在實際工程項目中滿足使用性能要求。許多研究人員開始對Dijkstra算法進行改進以提高算法的運行效率[2～8]，其中胡樹瑋從限制搜索范圍和限定搜索方向兩方面著手,在扇形區域內尋找最短路徑,對Dijkstra 算法優化改進，李元臣采用二叉樹結構來改進Dijkstra 算法，張福浩提出一種基于鄰接結點算法的Dijkstra優化算法，劉建美基于每個時段內的歷史平均速度給出了改進的Dijkstra優化算法，王樹西對Dijkstra標號法進行了改進，為解決最短路徑問題提供了切實可行的算法。本文在對傳統Dijkstra 算法進行詳細分析后，建立未標記節點數組，對Dijkstra算法的未標記節點遍歷過程進行改進，使得搜索過程不必全部遍歷或只較少地遍歷未標記結點，從而簡化搜索過程以降低時間復雜度，提高算法的運行效率。

1 Dijkstra算法基本思路

Dijkstra算法的基本思路是：假設每個點都有一對標號(dj,pj)，其中dj是從起源點s到點j的最短路徑的長度(從頂點到其本身的最短路徑是零路(沒有弧的路),其長度等于零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如圖1所示。

圖1 Dijkstra算法流程

1)初始化。起源點設置為：（1）ds=0,ps為空；（2）所有其他點:di=inf,pi=?；（3）標記起源點s，記k=s,其他所有點設為未標記的。

2)檢驗從所有已標記點k 到其直接連接未標記點j的距離，并設置：dj=min[dj,dk+lkj]式中,lkj是從點k到j的直接連接距離。

3)選取下一個點。從所有未標記的結點中,選取dj中最小的一個i:

di=min[ dj,所有未標記的點j]點i就被選為最短路徑中的一點,并設為已標記的。

4)找到點i的前一點。從已標記的點中找到直接連接到點i的點 j*，作為前一點，設置：i=j*。

5)標記點i。如果所有點已標記，則算法完全退出，否則，記k=i,轉到2)再繼續。

2 算法改進分析

為詳細介紹改進原理，以實例說明：假如某物流企業要將一批產品由A地運往F地，如圖2所示，在A、F 兩地的網絡圖中的點B、C、D、E 分別表示四個地名節點，點與點之間的連線表示兩地之間的公路，邊上權重代表兩地間的距離（當然在實際問題中邊的權重可以是費用，效率等其他優化目標權重），從A到F有多條路線選擇，怎樣選擇一條最優線路使運輸線路最短。

圖2 A到F點的網絡模型圖

第一，進入A，此時A為標記點，最短路徑為A→A=0，以A為中間點，從A開始找。其余點均為未標記點。A→B=6，A→C=3，A→其他U中的頂點=∞，發現A→C=3 權值為最短。

第二，進入C，此時A,C為標記點，最短路徑A→A=0，A→C=3，以C為中間點，從A→C=3這條最短路徑開始找。B，D，E，F為未標記點，A→C→B=5（比A→B=6要短），此時到B權值為A→C→B=5，A→C→D=6，A→C→E=7，A→C→其他U中的頂點=∞，發現A→C→B=5 權值為最短。

參照手術病理結果，單排螺旋CT檢出、診斷正確分別為134、133例，占比分別為98.53%、97.79%，差異無統計學意義（P＞0.05）；其中，椎間盤部分脫出、黃韌帶肥厚合并鈣化、椎間孔狹窄、硬膜囊受損、側隱窩狹窄各51、16、6、26、34例，見表1、表2。

第三，進入B，此時A，C，B為標記點，最短路徑A→A=0，A→C=3，A→C→B=5，以B為中間點，從A→C→B=5這條最短路徑開始找。D，E，F未標記，A→C→B→D=10（比第二步的A→C→D=6 要長），此時到D權值改為A→C→D=6，A→C→B→其他U中的頂點=∞，發現A→C→D=6權值為最短。

第四，進入D，此時A，C，B，D為標記點，最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6，以D為中間點，從A→C→D=6這條最短路徑開始找。E，F未標記，A→C→D→E=8（比第二步的A→C→E=7要長），此時到E權值更改為A→C→E=7，A→C→D→F=9，發現A→C→E=7權值為最短。

第五，進入E，此時A，C，B，D，E為標記點，最短路徑為A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E為中間點，從A→C→E=7這條最短路徑開始找。F未標記，A→C→E→F=12（比第四步的A→C→D→F=9要長），此時到F權值更改為A→C→D→F=9，發現A→C→D→F=9權值為最短。

第六，進入F，此時A，C，B，D，E，F為標記點，此時最短路徑為A→A=0，A→C=3，A →C →B=5，A →C →D=6，A →C →E=7，A→C→D→F=9。

第七，得到最短路徑。從第六步可知，從A 到F 的最短路徑為9公里，A 到B的最短路徑為A→C→B=5，A到C是最短路徑為A→C=3，A到D的最短路徑為A→C→D=6，A 到E 的最短路徑為A→C→E=7，所以A 到F 的最短路徑為A→C→D→F=9。從Dijkstra算法的基本思路可以看出，在求解從起點到某一終點的最短路徑的過程中，還可以得到從該起點到其他各結點的最短路徑。

普通Dijkstra算法在計算第二步的時候，一般都是對所有未標記的點進行遍歷，從第一個未標記的點計算到最后一個未標記的點。而計算完一個標記點，計算下一個標記點時，更新數據之后又要重新遍歷所有未標記的點，因此需要不斷循環遍歷所有的未標記結點,這無疑成為該算法的一個瓶頸。使得算法復雜度變為O(n^2)。

本文算法改進主要針對第二步，搜索過程不必全部遍歷或只較少地遍歷未標記結點，那么時間復雜度自然也就減少了。論文利用MATLAB構造find函數，一次找出所有未標記的點，組成一個數組，對整個數組進行計算處理，便可達到一次處理所有未標記點的效果。用一個指令便可完成一次循環操作，完成上述第二步：d(tb)=min(d(tb),d(temp)+W(k,tb))，其中tb為一個數組，即所有未標記的點。d為起始點到該點的距離，也是一個數組，k為第二步中的中間點，W為輸入的網絡拓撲關系圖。這樣，對于原來算法復雜度為O(n^2)就變成了O(n)。而對于MATLAB而言，處理一個數，和一個數組所用時間是差不多的。這便充分利用了MATLAB處理數組的優勢。

另外針對算法第五步，原算法要求計算直到所有點都為已標記點，我們只求從起始點到目的點的距離與路徑，如果目的點已經設為標記點，則說明，從起始點到目的點的最短距離已經計算出來，路徑也已經計算出來，完全沒有必要計算下去。因此，可以進行簡化，算法甚至不用循環n次就可計算出結果。

3 改進算法編程實現

調用改進Dijkstra 算法和調用一般Dijkstra 算法一樣，只需要輸入起始點，目的點，和網絡拓撲結構矩陣，就可得出從起始點到目的點的最短路徑距離，以及途徑的節點。以下是MATLAB編寫的優化算法主要程序。

可以看出，整個算法循環只有一次，而且，如果目的點不是最后一個標記點的話，算法循環要少于n次，使得時間復雜度大大降低，提高了運行效率，由于目標節點為結束標志，因此算法準確性也得到保證。

4 仿真實驗

本文的算法復雜度為O(n)，它與節點呈線性關系，當節點數目較大時，其優勢更加明顯。為了驗證基于MATLAB優化的迪杰斯特拉算法，搜索算法的效率，取不同網絡節點數測試該算法。測試環境配置為基于AMD Athlon(tm)64X2 Dual Core Processor 4600+2.40GHz CPU、1.87GB內存的普通常用計算機。表1為普通迪杰斯特拉算法與MATLAB優化的迪杰斯特拉算法在不同節點數時運行平均時間對比。

表1 普通Dijkstra與改進的Dijkstra算法平均時間比較（單位：秒）

圖3 Dijkstra與改進Dijkstra最短路徑計算時間比較分析

在大量測試數據下反復試驗測得，如圖3所示，當節點數量超過1000，普通迪杰斯特拉算法會變得很慢，在實際使用中難以忍受漫長等待，節點越多，等待時間更是成平方增長。而通過MATLAB優化改進的迪杰斯特拉算法，雖然也會隨著節點數目的增加，運行時間有所增加，但是，只是普通的線性增長，1000多個結點甚至不到1秒，相比原來，整整節省了40多秒！當節點數目超過2000甚至跟多，普通算法基本上很難以存在項目中使用了。下面是其中一次測試結果，第一個是改進的算法所花費的時間，第二個是普通算法所花費時間。明顯看出，在得到相同結果的情況下，Matlab優化算法大大提高了效率。（其中測試結點1139，1062是隨機選取的）。

5 結束語

本文給出了一種基于改進迪杰斯特拉算法實現網絡最短路徑快速尋優的方法，通過一次性處理所有未找到最短路徑的節點，一次性循環即可找到一個已知最短路徑的節點，使得所遍歷的未標記節點數量大幅度減少，促使時間復雜度降低為O(n)，優化了尋優過程。并利用了Matlab處理數組矩陣的優勢進行編程，測試數據的仿真實驗結果表明，算法改進后運行時間極大縮小，明顯提高了運行效率，為實際大規模網絡分析應用提供一種有效方法。

[1]田鈞.基于改進蟻群算法的物流配送應用研究[J].制造業自動化,2013,35(8):88-90.

[2]Sung K,Bell M,Seong M,et al.Shortest path in a network with time-dependent flow speeds[J].European Journal of Operational Research,2000,121(1):32-39.

[3]李元臣,劉維群.基于Dijkstra算法的網絡最短路徑分析[J].微計算機應用,2004(03):295-298.

[4]張福浩,劉紀平,李青元.基于Dijkstra算法的一種最短路徑優化算法[J].遙感信息,2004(02):38-41.

[5]胡樹瑋,張修如,趙洋.扇形優化Dijkstra算法[J].計算機技術與發展,2006(12):p.49-51.

[6]Xu M H,Liu Y Q,et al.An improved Dijkstra’s shortest path algorithm for sparse network[J].Applied Mathematics and Computation,2007,185(1):247-254.

[7]劉建美,馬壽峰,馬帥奇.基于改進的Dijkstra算法的動態最短路計算方法[J].系統工程理論與實踐,2011,31(6):1153-1157.

[8]王樹西,吳政學.改進的Dijkstra最短路徑算法及其應用研究[J].計算機科學,2012,39(5):223-228.