摘 要：傳統(tǒng)的Dijkstra算法一般用于計算一個源節(jié)點到所有其他節(jié)點的最小代價路徑，它能夠適應(yīng)網(wǎng)絡(luò)拓撲的變化，因而可以應(yīng)用在物流中的配送線路規(guī)劃上。原始的Dijkstra算法在實現(xiàn)時不僅占用大量計算機內(nèi)存，而且執(zhí)行效率也不高。針對這一問題，本文基于傳統(tǒng)的Dijkstra算法，對其數(shù)據(jù)存儲和算法思路進行了優(yōu)化。最終通過實驗證明優(yōu)化后的Dijkstra比原始的Dijkstra算法在執(zhí)行效率上有了較大的提高。

關(guān)鍵詞：Dijkstra算法；最短路徑；物流配送；優(yōu)化算法

中圖分類號：TP301.6

物流業(yè)的發(fā)展已成為國民經(jīng)濟的一個新的增長點，科學(xué)合理的物流業(yè)是經(jīng)濟可持續(xù)發(fā)展的重要部分，其發(fā)展程度已經(jīng)成為衡量一個國家現(xiàn)代化程度和綜合國力的重要標(biāo)志之一，被喻為促進經(jīng)濟增長的“第三利潤源泉”。在物流配送活動中，主要是把一批貨物從配送中心運送到一個或多個非固定客戶的接貨處。通常配送中心與客戶之間有多條運輸路線可以選擇。如果配送中心不進行運輸路線的合理規(guī)劃，往往會出現(xiàn)不合理的運輸現(xiàn)象，如迂回運輸、重復(fù)運輸?shù)?。不合理運輸會造成運輸成本上升。因此確定合理的配送路線，從而使運輸成本降低的同時又使服務(wù)水平得到改善是物流配送管理工作的一項重要內(nèi)容。

本論文是筆者在湖北某軟件公司實習(xí)期間，參與的一個物資綜合管理系統(tǒng)，其中有一個模塊是關(guān)于車輛調(diào)配和物流運輸?shù)?，然后在此基礎(chǔ)上實現(xiàn)基于Dijkstra算法并對其進行優(yōu)化的物流配送最短路徑選擇算法。通過實驗發(fā)現(xiàn)，不僅節(jié)約了物流成本，而且提高了運輸?shù)男省?/p>

1 Dijkstra算法介紹

1.1 Dijkstra算法思想及步驟

Dijkstra算法用于計算一個源節(jié)點到所有其他節(jié)點的最短代價路徑，它是按路徑長度遞增的次序來產(chǎn)生最短路徑的算法。該算法的輸入包含一個有權(quán)重的有向圖G以及G中的一個頂點s，用V表示G中所有頂點的集合，S表示已求得最短路徑的值頂點，w（u，v）表示從頂點u到頂點v的權(quán)重（設(shè)定權(quán)重均為非負值），（u，v）表示從頂點u到頂點v有路徑相連，d（v）表示從頂點s到頂點v的最小權(quán)重。步驟如下：

（1）初始時，集合S只包含頂點s，s的路徑長度值被賦為0（即d（s）=0），選擇頂點m，若存在能直接到達的邊（s，m），則d（m）=min{w（s，m）}，并將頂點m加入集合S，對于所（1）Dijkstra算法的效率與頂點數(shù)N密切相關(guān)。

（2）在存儲圖形數(shù)據(jù)和運算時，需要定義N*N的數(shù)組，其中N為網(wǎng)絡(luò)的結(jié)點數(shù)，當(dāng)網(wǎng)絡(luò)的結(jié)點數(shù)較大時，將占用大量的計算機內(nèi)存。

（3）當(dāng)從未標(biāo)記節(jié)點集合（V-S）選定下一個頂點m作中間節(jié)點后，在更新最短路徑的過程中，需要掃描所有的未標(biāo)記節(jié)點并進行比較更新。而未標(biāo)記節(jié)點集合（V-S）中往往包含大量與中間點m不直接相連的節(jié)點，即Cost[j，k]=∞。因而很多操作無效而導(dǎo)致執(zhí)行效率降低。

2 Dijkstra算法優(yōu)化

2.1 數(shù)據(jù)存儲的優(yōu)化

通常在一個城市交通圖模擬出來的網(wǎng)絡(luò)圖中，存在很多頂點（物流運輸?shù)牡攸c）和邊（道路），而且錯綜復(fù)雜，但真正與某一頂點相關(guān)的邊和頂點是有限的。以鄰接矩陣或關(guān)聯(lián)矩陣為基礎(chǔ)的算法中，存在著很多權(quán)值為∞的元素，這些無效的元素占用了大量的計算機內(nèi)存。如果在表示網(wǎng)絡(luò)結(jié)構(gòu)圖的關(guān)系時，只是記錄與某一頂點相關(guān)的邊和頂點，這樣就可以減少很多無效的權(quán)值為∞的頂點，從而起到節(jié)約內(nèi)存的作用。具體步驟如下：

（1）依據(jù)最大相鄰頂點數(shù)的概念，計算出網(wǎng)絡(luò)圖中的最大相鄰頂點數(shù)m；

（2）根據(jù)網(wǎng)絡(luò)圖構(gòu)造鄰接矩陣。以網(wǎng)絡(luò)圖中的頂點為行，以該頂點相鄰的點為列，矩陣的行數(shù)為網(wǎng)絡(luò)圖中的實際頂點數(shù)，列數(shù)為網(wǎng)絡(luò)圖中的最大相鄰頂點數(shù)m，改鄰接矩陣中的值為與行頂點相連的頂點值。如果該頂點的相鄰頂點數(shù)少于最大相鄰頂點數(shù)m，則用0代替。

（3）根據(jù)網(wǎng)絡(luò)圖構(gòu)造判斷矩陣。對照上一步構(gòu)造出來的鄰接矩陣，用鄰接矩陣?yán)锏母鱾€元素對應(yīng)邊號的權(quán)值代替同一位置的頂點值就構(gòu)成了判斷矩陣；

（4）然后根據(jù)鄰接矩陣和判斷矩陣求網(wǎng)絡(luò)圖上某一頂點到其他頂點間的最短路徑。

2.2 算法思路的優(yōu)化

傳統(tǒng)的Dijkstra算法能求出網(wǎng)絡(luò)圖中的最短路徑，但是在頂點和邊很多的情況下，該算法需要遍歷很多節(jié)點，而且很多是無效的頂點，所以執(zhí)行效率比較低。其主要表現(xiàn)在：更新新加入的頂點m到集合V—S中所有頂點的最短路徑時，需要大量比較d[m] + w[m，v]和d[v]的大小，而此時很多頂點并不與m相鄰（即w[m，v]=∞），這樣就增加了額外的運算量。由于Dijkstra算法是計算從起點到某一頂點的最短路徑，我們也可以將其表述為計算從某一頂點到起點的最短路徑。因此求最短路徑問題可以分解兩個子問題，即計算由起點到終點的最短路徑和由終點到起點的最短路徑，這樣就大大降低了求解最短路徑問題的復(fù)雜度。

傳統(tǒng) Dijkstra算法在提取最短路徑節(jié)點時需要遍歷所有的在集合V—S中的頂點，并更新最短路徑值，所以算法的實踐復(fù)雜度為O（N2）。而本文改進的算法將此問題分解為兩個子問題進行求解，而且符合并行處理思想。這樣對執(zhí)行速度有了較大的提高，特別是對于網(wǎng)絡(luò)圖中頂點數(shù)和邊較多的情況下。

3 結(jié)束語

在物流配送中，合理的配送路線規(guī)劃不僅能夠及時地滿足客戶的需求，而且可以節(jié)約配送中心的運輸成本，所以求出最短配送路徑算法的效率具有重要的作用。本文結(jié)合配送路線規(guī)劃的實際情況，選擇Dijkstra算法作為物流配送路線規(guī)劃的核心算法，并對它的不足提出了優(yōu)化方法，在數(shù)據(jù)存儲和算法思路兩個方面進行了優(yōu)化，使優(yōu)化后的算法能夠提高配送路線規(guī)劃的效率。最后經(jīng)實驗證明，優(yōu)化后的Dijkstra算法不僅節(jié)約了物流成本，而且提高了運輸效率。

參考文獻：

[1]嚴(yán)蔚敏，吳偉明.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2009.

[2]李臣波.一種基于Dijkstra的最短路徑算法[J].哈爾濱理工大學(xué)學(xué)報，2008.

[3]李怡，張鐵柱，滕春賢.基于GIS的配送車輛路線規(guī)劃的研究[J].哈爾濱理工大學(xué)學(xué)報，2006，11

作者簡介：鐘寶榮（1963-），通信作者，教授，1992年華中理工大學(xué)計算機軟件專業(yè)碩士畢業(yè)，主要研究方向為：網(wǎng)絡(luò)數(shù)據(jù)庫技術(shù)、圖形圖象處理技術(shù)、多媒體數(shù)據(jù)通信技術(shù)等。

作者單位：長江大學(xué)計算機科學(xué)學(xué)院，湖北荊州 434023