矩陣迭代和Dijkstra兩種算法在交通運(yùn)輸路徑選擇中的對(duì)比

本文基于矩陣迭代算法及Dijkstra算法，對(duì)兩者在最短路徑問題中的差異性進(jìn)行了對(duì)比。結(jié)果表明：Dijkstra算法可一次求得一點(diǎn)到其他各點(diǎn)的最小阻抗，該算法在進(jìn)行最短路徑的計(jì)算時(shí)，需要對(duì)相鄰點(diǎn)進(jìn)行反復(fù)搜尋，計(jì)算效率較低，收斂速度較慢。矩陣迭代算法沒有嚴(yán)格路徑次序限制迭代順序，可實(shí)現(xiàn)算法并行計(jì)算，計(jì)算速度較高。在阻抗矩陣為對(duì)稱矩陣時(shí)，在經(jīng)過迭代后，得到的矩陣仍為對(duì)稱矩陣，這樣可使每次迭代的計(jì)算量得到減少。通過在重慶市路網(wǎng)上隨機(jī)選取8個(gè)終點(diǎn)及起點(diǎn)，對(duì)起始點(diǎn)1點(diǎn)到8點(diǎn)的最短路徑及阻抗進(jìn)行計(jì)算表明，Dijkstra算法所用時(shí)間為0.673s，迭代矩陣算法所用時(shí)間為0.501s，矩陣迭代算法的計(jì)算速度更快。在矩陣4×4、6×6、8×8中，矩陣迭代算法的運(yùn)算時(shí)間均比Dijkstra算法的運(yùn)算時(shí)間要小，其迭代次數(shù)次數(shù)也遠(yuǎn)遠(yuǎn)小于Dijkstra算法的迭代次數(shù)，這進(jìn)一步表明，矩陣迭代算法的計(jì)算效率要比Dijkstra算法的計(jì)算效率高。

【關(guān)鍵詞】Dijkstra算法 矩陣迭代算法 交通 阻抗

1 引言

隨著我國經(jīng)濟(jì)發(fā)展越來越快，城市交通運(yùn)輸路徑也日趨緊張，在我國大中型城市中，普遍存在公共交通結(jié)構(gòu)的不合理狀況[1-4]。城市公共交通網(wǎng)絡(luò)由眾多路徑及網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)成。由于城市人口和城市規(guī)模的不斷增長，優(yōu)化交通運(yùn)輸路徑，解決交通出行者出行時(shí)間最小、服務(wù)最大化、線網(wǎng)效率最大等，方便居民出行[5-7]。在城市交通嚴(yán)重堵塞時(shí)，要使交通出行者出行便利，則必須對(duì)最短交通路徑及交通狀態(tài)信息進(jìn)行實(shí)時(shí)全面了解；在一定程度上，這種信息誘導(dǎo)作用能對(duì)重點(diǎn)道路的擁堵起到緩解作用[8]。最短路徑的算法有多種，對(duì)各種算法進(jìn)行分析、理解、應(yīng)用，比較這些算法的在實(shí)際應(yīng)用效率，具有非常重要的實(shí)用意義[9-11]。通常情況下，典型最短路徑問題算法有兩種，分別為矩陣迭代算法、Dijkstra算法。本文基于這兩種典型算法，對(duì)兩者在最短路徑問題中的差異性進(jìn)行了對(duì)比，方便交通出行者對(duì)交通運(yùn)輸路徑的選擇。

2 最短路徑及路網(wǎng)阻抗

在交通流分配中，最基本的算法就是最短路徑算法。最短路徑是指在一個(gè)網(wǎng)絡(luò)中，已知相鄰節(jié)點(diǎn)間的線路長度，要在某一起點(diǎn)到某一終點(diǎn)間找出一條長度最短的路線。在交通領(lǐng)域，最短路徑研究較多，在路網(wǎng)中，因受道路條件、道路繞行距離、交通條件影響，使得不同交通路徑，所需交通費(fèi)用有一定的差異。在廣義上，交通費(fèi)用包括道路通行時(shí)間、通行距離、燃料的使用等；在狹義上，道路通行時(shí)間是阻抗，或?qū)⒂绊懗鲂械钠渌蛩剡M(jìn)行折算，轉(zhuǎn)化成通行時(shí)間，將其作為道路網(wǎng)交通阻抗，交通阻抗最小的路徑就是最短路徑。圖1為路網(wǎng)的阻抗，表1為道路的可用阻抗矩陣。

3 Dijkstra算法和矩陣迭代算法

3.1 Dijkstra算法

最短路徑使用最廣泛、最基本的算法就是Dijkstra算法，在求網(wǎng)絡(luò)中某一節(jié)點(diǎn)到其他各節(jié)點(diǎn)的最短路徑時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)被Dijkstra算法分成三部分，分別為最短路徑節(jié)點(diǎn)、臨時(shí)標(biāo)記節(jié)點(diǎn)、未標(biāo)記節(jié)點(diǎn)。在算法開始時(shí)，源點(diǎn)經(jīng)初始化，轉(zhuǎn)為最短路徑節(jié)點(diǎn)，其他節(jié)點(diǎn)則為未標(biāo)記節(jié)點(diǎn)。在執(zhí)行算法時(shí)，從最短路徑節(jié)點(diǎn)擴(kuò)展到相鄰節(jié)點(diǎn)，非最短路徑節(jié)點(diǎn)的相鄰節(jié)點(diǎn)每次都要修改為臨時(shí)標(biāo)記節(jié)點(diǎn)，對(duì)權(quán)值是否更新進(jìn)行判斷，權(quán)值最小節(jié)點(diǎn)從全部的臨時(shí)標(biāo)記節(jié)點(diǎn)中提取，在修改為最短路徑節(jié)點(diǎn)后，將其作為下次擴(kuò)展源，重復(fù)前面步驟，在全部的節(jié)點(diǎn)做過擴(kuò)展源后，結(jié)束算法。

Dijkstra算法屬于比較經(jīng)典的最短路徑算法，它可對(duì)一點(diǎn)到網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)最小阻抗進(jìn)行計(jì)算，并將相應(yīng)最短路徑推算出。Dijkstra算法計(jì)算步驟共5步，第一步是將Dijkstra算法起始點(diǎn)進(jìn)行標(biāo)號(hào)，記為P，且P（o）=0，其余節(jié)點(diǎn)標(biāo)號(hào)為T，且除T（0）外，其余節(jié)點(diǎn)的T（i）=∞；第二步是將o點(diǎn)相鄰點(diǎn)向量r找出，即dor（i）≠∞，對(duì)所有標(biāo)號(hào)為T的值進(jìn)行比較，找出最小值，即P（k），T最小時(shí)所在的點(diǎn)為k點(diǎn)；第三步是按照第二步方法，將k作為起始點(diǎn)，滿足T（r（j））=minT（r（j）），P（k）+dkr（i），將最小值所在點(diǎn)k/找出，記P（k/）；第四步是迭代第三步，在全部節(jié)點(diǎn)被標(biāo)志為P后，則求出了o點(diǎn)到其余節(jié)點(diǎn)的最小阻抗；第五步是根據(jù)所需，對(duì)目標(biāo)點(diǎn)進(jìn)行查詢，以目標(biāo)點(diǎn)d為起始點(diǎn)，將滿足式P（j）=dij+P（i）的i點(diǎn)找出，最短路徑中j的前一點(diǎn)就是i點(diǎn)，對(duì)i點(diǎn)之前的點(diǎn)進(jìn)行繼續(xù)搜索，同樣根據(jù)P（j）=dij+P（i），直到搜索起點(diǎn)o，圖2為Dijkstra算法程序流程圖。

3.2 矩陣迭代算法

矩陣迭代算法首先要構(gòu)造距離矩陣，在矩陣中，給出了節(jié)點(diǎn)間經(jīng)過一步到達(dá)某一點(diǎn)的距離，見圖3，通過距離矩陣的迭代運(yùn)算，兩步到達(dá)某一點(diǎn)的最短距離就得到了。因此，使用矩陣迭代算法研究最短路徑問題時(shí)，各出行節(jié)點(diǎn)間最短路線要知道。

在D（4）=D（3）時(shí)，具有最短距離矩陣，通過矩陣，可將最短距離計(jì)算出。通過反向追蹤，對(duì)相應(yīng)最短路線進(jìn)行確定。

矩陣迭代法指的是從路徑集合中進(jìn)行挑選，將最短路徑分步選出來，完成矩陣迭代，則表明可計(jì)算出每一對(duì)od點(diǎn)間的最短路徑。迭代矩陣算法思想類似于Dijkstra，不同的是其采用矩陣形式對(duì)最短路徑問題的進(jìn)行思考，也就是在od兩點(diǎn)間，嘗試性選擇中間路徑，計(jì)算每個(gè)可能的中間路徑，并將最小節(jié)點(diǎn)選出，并進(jìn)行迭代計(jì)算，得出到達(dá)該最短路徑是要經(jīng)過幾個(gè)中間節(jié)點(diǎn)。當(dāng)所有節(jié)點(diǎn)最短路徑迭代全部求出后，矩陣迭代結(jié)果保持穩(wěn)定，不再變化，這時(shí)表明迭代結(jié)束。

矩陣迭代算法的計(jì)算步驟共4步，第一步是給定od，其阻抗方陣為D，D1=D，按照公式dij（2）=min（di1（1）+d1j，di2（1）+d2j，…，din（1）+dnj），n表示矩陣階數(shù)n，i=1～n，j=1～n。根據(jù)此公式，將兩步到達(dá)目的地最小阻抗計(jì)算出，D2為得到的新矩陣。當(dāng)dik+dkj達(dá)到最小時(shí)，將k值記為k（1），也就是最短路徑中的一點(diǎn)；第二步是根據(jù)公式dij（3）=min（di1（2）+d1j，di2（2）+d2j，…，din（2）+dnj），n表示矩陣階數(shù)n，i=1～n，j=1～n，得到D3。最小值對(duì)應(yīng)點(diǎn)記為k（2）；第三步則依次類推，dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩陣階數(shù)n，i=1～n，j=1～n，得到Dm，最小值對(duì)應(yīng)點(diǎn)記為k（m-1），直到Dm=Dm-1；第四步是對(duì)目標(biāo)最小阻抗od即dodm進(jìn)行搜索，i、j兩點(diǎn)間最小阻抗表示為dijm。在標(biāo)志點(diǎn)o，k（1），k（2），…，k（m-1），d中，選取最短路徑，為避免某些點(diǎn)會(huì)出現(xiàn)重復(fù)，按照didm=dik+dkdm的路徑順序原則進(jìn)行確定，i起始于o點(diǎn)，根據(jù)標(biāo)志點(diǎn)順序，依次進(jìn)行檢驗(yàn)，最短路徑就是符合要求的點(diǎn)向量。圖4為矩陣迭代算法程序流程圖。

4 兩種算法的比較

通過MatLab平臺(tái)，進(jìn)行矩陣迭代算法、Dijkstra算法的編程，MatLab能將計(jì)算過程及結(jié)果顯示出來，通過profiler功能，能將計(jì)算時(shí)間顯示出來。

4.1 最短路徑收斂性

矩陣迭代算法、Dijkstra算法的收斂特性由路阻矩陣及計(jì)算思路特點(diǎn)決定。因此，使用用計(jì)算機(jī)計(jì)算是可行的。在相鄰節(jié)點(diǎn)，Dijkstra尋找過程中，向目標(biāo)節(jié)點(diǎn)步步靠近，當(dāng)最后的終止條件滿足后，達(dá)到查詢終點(diǎn)，起始點(diǎn)到其他點(diǎn)的最小路徑能計(jì)算出。因路阻矩陣特殊性，在矩陣迭代算法中，矩陣對(duì)角線位置元素均為零，目標(biāo)節(jié)點(diǎn)就是最終收斂點(diǎn)，矩陣收斂的充要條件是對(duì)角線上的零元素。

4.2 兩種方法異同點(diǎn)

相比于矩陣迭代算法而言，使用Dijkstra算法，可將一點(diǎn)到其他各點(diǎn)的最小阻抗一次性求得，根據(jù)最短路徑，最短路徑經(jīng)過的節(jié)點(diǎn)可依次得到，在進(jìn)行最短路徑的計(jì)算時(shí)，需要反復(fù)進(jìn)行，同時(shí)不能顛倒起始點(diǎn)到其他各點(diǎn)最小阻抗的計(jì)算順序，按照步驟嚴(yán)格進(jìn)行，因而，Dijkstra算法計(jì)算效率低，收斂速度較慢。相比于Dijkstra算法而言，矩陣迭代算法則非常簡潔，要求不苛刻，矩陣迭代計(jì)算效率提高的方法有三個(gè)比較可行。第1個(gè)是在矩陣迭代算法中，每一步只要遵循dij（m）=min（di1（m-1）+d1j，di2（m-1）+d2j，…，din（m-1）+dnj），n表示矩陣階數(shù)n，i=1～n，j=1～n原則，在i，j間，其迭代順序限制不嚴(yán)格，可并行進(jìn)行計(jì)算，這樣就可使計(jì)算速度大大提高；第2個(gè)是可以同時(shí)設(shè)計(jì)程序，使計(jì)算值避免出現(xiàn)∞數(shù)據(jù)，只對(duì)非∞數(shù)據(jù)與其下標(biāo)策略進(jìn)行存取，這樣內(nèi)存空間就得到節(jié)約，從而使計(jì)算效率得到提高；第3個(gè)由于阻抗矩陣屬于對(duì)稱矩陣，在不斷進(jìn)行迭代后，阻抗矩陣仍屬于對(duì)稱矩陣，根據(jù)這一特征，每次迭代的計(jì)算量可減少。若道路阻抗是負(fù)數(shù)，則可能Dijkstra算法會(huì)出現(xiàn)無效，在矩陣迭代算法中，道路阻抗可為負(fù)數(shù)，圖5為矩陣迭代算法中的道路阻抗。

4.3 計(jì)算效率比較

在計(jì)算程序中，MatLab內(nèi)含的程序測試器profiler，具有一定的優(yōu)越性，因此本研究采用MatLab平臺(tái)進(jìn)行Dijkstra算法、矩陣迭代算法的編程，并計(jì)算同一路網(wǎng)，在得到相同結(jié)果時(shí)，對(duì)各個(gè)計(jì)算效率指標(biāo)進(jìn)行比較，在計(jì)算效率方面，顯示Dijkstra算法、矩陣迭代算法的不同。在重慶市路網(wǎng)上隨機(jī)選取8個(gè)終點(diǎn)及起點(diǎn)，對(duì)起始點(diǎn)1點(diǎn)到8點(diǎn)的最短路徑及阻抗進(jìn)行計(jì)算。在程序算法分析里，時(shí)間復(fù)雜度是非常重要的內(nèi)容，時(shí)間復(fù)雜度通常是指算法中執(zhí)行基本運(yùn)算的次數(shù)，影響時(shí)間復(fù)雜度的因素較多，本研究主要對(duì)影響時(shí)間復(fù)雜度的重要因素進(jìn)行分析，比較Dijkstra算法、矩陣迭代算法的時(shí)間復(fù)雜度，表2為兩種方法計(jì)算時(shí)間，表3為Dijkstra算法的計(jì)算結(jié)果，表 4為矩陣迭代算法計(jì)算結(jié)果。

對(duì)起始1點(diǎn)到8點(diǎn)的最小路阻采用Dijkstra算法進(jìn)行計(jì)算，結(jié)果為P（8）=5，其相應(yīng)的最短路徑為1→4→5→6→8。對(duì)起始1點(diǎn)到8點(diǎn)的最小路阻采用迭代矩陣算法進(jìn)行計(jì)算，結(jié)果為D1（1，8）=5，其相應(yīng)的最短路徑為1→4→5→6→8，結(jié)果相同。但Dijkstra算法和迭代矩陣算法的計(jì)算效率有一定的差距，從表2可以看出，Dijkstra算法所用時(shí)間為0.673s，迭代矩陣算法所用時(shí)間為0.501s，矩陣迭代算法的計(jì)算速度更快。矩陣迭代法可全部算出路網(wǎng)中兩點(diǎn)間的最小阻抗，Dijkstra算法僅能算出起始點(diǎn)到其他各點(diǎn)間的最小路阻；路網(wǎng)中的節(jié)點(diǎn)遠(yuǎn)比8多很多，采用Dijkstra算法要進(jìn)行上萬次的循環(huán)，使計(jì)算速度大幅降低，使用迭代矩陣算法，則迭代次數(shù)遠(yuǎn)比節(jié)點(diǎn)數(shù)小，因此，迭代矩陣算法優(yōu)勢更大，同時(shí)對(duì)于路阻為負(fù)的路網(wǎng)，可通過矩陣迭代進(jìn)行計(jì)算，即對(duì)于更廣泛的最短路徑，迭代矩陣算法能適合其計(jì)算要求。

基本運(yùn)算次數(shù)與運(yùn)算所需時(shí)間的乘積即就是算法執(zhí)行時(shí)間，為進(jìn)一步比較Dijkstra算法和迭代矩陣算法的計(jì)算效率，本研究將兩程序?qū)χ腥〕?×4、6×6、8×8共3個(gè)矩陣進(jìn)行計(jì)算，對(duì)運(yùn)算時(shí)間進(jìn)行比較，分別對(duì)交通運(yùn)輸路網(wǎng)中任意2點(diǎn)間的最小阻抗進(jìn)行計(jì)算，表5為計(jì)算時(shí)間參數(shù)數(shù)據(jù)。

從表5可以看出，在矩陣4×4、6×6、8×8中，矩陣迭代算法的運(yùn)算時(shí)間均比Dijkstra算法的運(yùn)算時(shí)間要小，其迭代次數(shù)次數(shù)也遠(yuǎn)遠(yuǎn)小于Dijkstra算法的迭代次數(shù)，這進(jìn)一步表明，矩陣迭代算法的計(jì)算效率要比Dijkstra算法的計(jì)算效率高。

5 結(jié)論

本文基于矩陣迭代算法及Dijkstra算法，對(duì)兩者在最短路徑問題中的差異性進(jìn)行了對(duì)比，得出以下結(jié)論：

（1）通過Dijkstra算法，對(duì)于一點(diǎn)到其他各點(diǎn)的最小阻抗可一次求得，最短路徑經(jīng)過的節(jié)點(diǎn)可依次得到，該算法在進(jìn)行最短路徑的計(jì)算時(shí)，需要對(duì)相鄰點(diǎn)進(jìn)行反復(fù)搜尋，計(jì)算效率較低，收斂速度較慢。

（2）矩陣迭代算法是元素間比較、數(shù)列間相加的過程，特點(diǎn)是簡單快捷。矩陣迭代算法沒有嚴(yán)格路徑次序限制迭代順序，可實(shí)現(xiàn)算法并行計(jì)算，計(jì)算速度較高。在阻抗矩陣為對(duì)稱矩陣時(shí)，在經(jīng)過迭代后，得到的矩陣仍為對(duì)稱矩陣，這樣可使每次迭代的計(jì)算量得到減少。

（3）通過在重慶市路網(wǎng)上隨機(jī)選取8個(gè)終點(diǎn)及起點(diǎn)，對(duì)起始點(diǎn)1點(diǎn)到8點(diǎn)的最短路徑及阻抗進(jìn)行計(jì)算表明，Dijkstra算法所用時(shí)間為0.673s，迭代矩陣算法所用時(shí)間為0.501s，矩陣迭代算法的計(jì)算速度更快。在矩陣4×4、6×6、8×8中，矩陣迭代算法的運(yùn)算時(shí)間均比Dijkstra算法的運(yùn)算時(shí)間要小，其迭代次數(shù)次數(shù)也遠(yuǎn)遠(yuǎn)小于Dijkstra算法的迭代次數(shù)，這進(jìn)一步表明，矩陣迭代算法的計(jì)算效率要比Dijkstra算法的計(jì)算效率高。

參考文獻(xiàn)

[1]張美玉，簡琤峰，侯向輝，等.Dikstra算法在多約束農(nóng)產(chǎn)品配送最優(yōu)路徑中的研究應(yīng)用[J]，浙江工業(yè)大學(xué)學(xué)報(bào)，2012，40（03）：321-326.

[2]Niehols，Jolin M.A major urban earthquake： planning for arma-geddon[J]，Landscape and Urban， 2005，73，2：136-154.

[3]劉洪麗，顧銘.矩陣迭代法在物流中心選址中的應(yīng)用分析[J]，現(xiàn)代商貿(mào)工業(yè)，2013（20）：64-67.

[4]丁浩，萇道方.基于Dijkstra算法的快遞車輛配送路徑優(yōu)化[J]，價(jià)值工程，2014（03）：15-18.

[5]郭瑞軍，王晚香.基于矩陣迭代法的出租車合乘最短路徑選擇[J]，大連交通大學(xué)學(xué)報(bào)，2011，32（04）：28-32.

[6]任鵬飛，秦貴和，董勁男，等.具有交通規(guī)則約束的改進(jìn)Dijkstra算法[J]，計(jì)算機(jī)應(yīng)用，2015，35（09）：2503-2507.

[7]王樹西.改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J]，計(jì)算機(jī)科學(xué)，2012，39（05）：223-228.

[8]劉春年，鄧青菁.應(yīng)急決策信息系統(tǒng)最優(yōu)路徑研究-基于路阻函數(shù)理論及Dijkstra算法[J]，災(zāi)害學(xué)，2014（03）：7.

[9]潘若愚，褚偉，楊善林.基于Dijkstra-PD-ACO算法的大城市公交線路優(yōu)化與評(píng)價(jià)方法研究[J]，中國管理科學(xué)，2015，23（09）：106-116.

[10]王佳，符卓.綜合客運(yùn)樞紐接運(yùn)公交線路優(yōu)化設(shè)計(jì)[J]，系統(tǒng)工程，2012，30（05）：101-106.

[11]高明霞.基于雙層規(guī)劃的交通疏散中車輛出發(fā)與交通控制綜合優(yōu)化[J]，中國管理科學(xué)，2014，22（12）：65-71.

作者簡介

肖鵬（1980-），男，江蘇省鎮(zhèn)江市人。碩士學(xué)位。現(xiàn)為江蘇城鄉(xiāng)建設(shè)職業(yè)學(xué)院基礎(chǔ)部講師。研究方向?yàn)閼?yīng)用數(shù)學(xué)。

作者單位

江蘇城鄉(xiāng)建設(shè)職業(yè)學(xué)院 江蘇省常州市 213147