矩陣迭代和Dijkstra兩種算法在交通運輸路徑選擇中的對比

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

【關鍵詞】Dijkstra算法 矩陣迭代算法 交通 阻抗

1 引言

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

2 最短路徑及路網阻抗

在交通流分配中，最基本的算法就是最短路徑算法。最短路徑是指在一個網絡中，已知相鄰節點間的線路長度，要在某一起點到某一終點間找出一條長度最短的路線。在交通領域，最短路徑研究較多，在路網中，因受道路條件、道路繞行距離、交通條件影響，使得不同交通路徑，所需交通費用有一定的差異。在廣義上，交通費用包括道路通行時間、通行距離、燃料的使用等；在狹義上，道路通行時間是阻抗，或將影響出行的其它因素進行折算，轉化成通行時間，將其作為道路網交通阻抗，交通阻抗最小的路徑就是最短路徑。圖1為路網的阻抗，表1為道路的可用阻抗矩陣。

3 Dijkstra算法和矩陣迭代算法

3.1 Dijkstra算法

最短路徑使用最廣泛、最基本的算法就是Dijkstra算法，在求網絡中某一節點到其他各節點的最短路徑時，網絡中的節點被Dijkstra算法分成三部分，分別為最短路徑節點、臨時標記節點、未標記節點。在算法開始時，源點經初始化，轉為最短路徑節點，其他節點則為未標記節點。在執行算法時，從最短路徑節點擴展到相鄰節點，非最短路徑節點的相鄰節點每次都要修改為臨時標記節點，對權值是否更新進行判斷，權值最小節點從全部的臨時標記節點中提取，在修改為最短路徑節點后，將其作為下次擴展源，重復前面步驟，在全部的節點做過擴展源后，結束算法。

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

3.2 矩陣迭代算法

矩陣迭代算法首先要構造距離矩陣，在矩陣中，給出了節點間經過一步到達某一點的距離，見圖3，通過距離矩陣的迭代運算，兩步到達某一點的最短距離就得到了。因此，使用矩陣迭代算法研究最短路徑問題時，各出行節點間最短路線要知道。

在D（4）=D（3）時，具有最短距離矩陣，通過矩陣，可將最短距離計算出。通過反向追蹤，對相應最短路線進行確定。

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

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

4 兩種算法的比較

通過MatLab平臺，進行矩陣迭代算法、Dijkstra算法的編程，MatLab能將計算過程及結果顯示出來，通過profiler功能，能將計算時間顯示出來。

4.1 最短路徑收斂性

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

4.2 兩種方法異同點

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

4.3 計算效率比較

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

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

基本運算次數與運算所需時間的乘積即就是算法執行時間，為進一步比較Dijkstra算法和迭代矩陣算法的計算效率，本研究將兩程序對中取出4×4、6×6、8×8共3個矩陣進行計算，對運算時間進行比較，分別對交通運輸路網中任意2點間的最小阻抗進行計算，表5為計算時間參數數據。

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

5 結論

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

（1）通過Dijkstra算法，對于一點到其他各點的最小阻抗可一次求得，最短路徑經過的節點可依次得到，該算法在進行最短路徑的計算時，需要對相鄰點進行反復搜尋，計算效率較低，收斂速度較慢。

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

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

參考文獻

[1]張美玉，簡琤峰，侯向輝，等.Dikstra算法在多約束農產品配送最優路徑中的研究應用[J]，浙江工業大學學報，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]劉洪麗，顧銘.矩陣迭代法在物流中心選址中的應用分析[J]，現代商貿工業，2013（20）：64-67.

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

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

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

[7]王樹西.改進的Dijkstra最短路徑算法及其應用研究[J]，計算機科學，2012，39（05）：223-228.

[8]劉春年，鄧青菁.應急決策信息系統最優路徑研究-基于路阻函數理論及Dijkstra算法[J]，災害學，2014（03）：7.

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

[10]王佳，符卓.綜合客運樞紐接運公交線路優化設計[J]，系統工程，2012，30（05）：101-106.

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

作者簡介

肖鵬（1980-），男，江蘇省鎮江市人。碩士學位。現為江蘇城鄉建設職業學院基礎部講師。研究方向為應用數學。

作者單位

江蘇城鄉建設職業學院 江蘇省常州市 213147