一種基于改進(jìn)Dijkstra的物流網(wǎng)絡(luò)路徑優(yōu)化算法分析

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

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

（南昌大學(xué) 機(jī)電工程學(xué)院，南昌 330031）

0 引言

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

1 Dijkstra算法基本思路

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

圖1 Dijkstra算法流程

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

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

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

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

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

5)標(biāo)記點i。如果所有點已標(biāo)記，則算法完全退出，否則，記k=i,轉(zhuǎn)到2)再繼續(xù)。

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

為詳細(xì)介紹改進(jìn)原理，以實例說明：假如某物流企業(yè)要將一批產(chǎn)品由A地運(yùn)往F地，如圖2所示，在A、F 兩地的網(wǎng)絡(luò)圖中的點B、C、D、E 分別表示四個地名節(jié)點，點與點之間的連線表示兩地之間的公路，邊上權(quán)重代表兩地間的距離（當(dāng)然在實際問題中邊的權(quán)重可以是費(fèi)用，效率等其他優(yōu)化目標(biāo)權(quán)重），從A到F有多條路線選擇，怎樣選擇一條最優(yōu)線路使運(yùn)輸線路最短。

圖2 A到F點的網(wǎng)絡(luò)模型圖

第一，進(jìn)入A，此時A為標(biāo)記點，最短路徑為A→A=0，以A為中間點，從A開始找。其余點均為未標(biāo)記點。A→B=6，A→C=3，A→其他U中的頂點=∞，發(fā)現(xiàn)A→C=3 權(quán)值為最短。

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

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

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

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

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

第六，進(jìn)入F，此時A，C，B，D，E，F(xiàn)為標(biāo)記點，此時最短路徑為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算法的基本思路可以看出，在求解從起點到某一終點的最短路徑的過程中，還可以得到從該起點到其他各結(jié)點的最短路徑。

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

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

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

3 改進(jìn)算法編程實現(xiàn)

調(diào)用改進(jìn)Dijkstra 算法和調(diào)用一般Dijkstra 算法一樣，只需要輸入起始點，目的點，和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣，就可得出從起始點到目的點的最短路徑距離，以及途徑的節(jié)點。以下是MATLAB編寫的優(yōu)化算法主要程序。

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

4 仿真實驗

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

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

圖3 Dijkstra與改進(jìn)Dijkstra最短路徑計算時間比較分析

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

5 結(jié)束語

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

[1]田鈞.基于改進(jìn)蟻群算法的物流配送應(yīng)用研究[J].制造業(yè)自動化,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算法的網(wǎng)絡(luò)最短路徑分析[J].微計算機(jī)應(yīng)用,2004(03):295-298.

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

[5]胡樹瑋,張修如,趙洋.扇形優(yōu)化Dijkstra算法[J].計算機(jī)技術(shù)與發(fā)展,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]劉建美,馬壽峰,馬帥奇.基于改進(jìn)的Dijkstra算法的動態(tài)最短路計算方法[J].系統(tǒng)工程理論與實踐,2011,31(6):1153-1157.

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