一種基于二叉堆的Dijkstra 最短路徑優化方法

王芝麟, 喬新輝, 馬 旭, 嚴 研

(1. 國網陜西省電力有限公司，西安 710048; 2. 北京洛斯達數字遙感技術有限公司，北京 100120)

1 引言

Dijkstra 算法是一種典型的最短路徑算法，可以在有向圖中實現最短路徑規劃.它的出現，解決了當時十分棘手的動態路徑規劃問題[1].隨著地理信息科學技術和計算機網絡技術的發展，最短路徑在今天的交通運輸、物流倉儲和城市規劃等領域仍然發揮著巨大的作用.二叉堆是一種數據項按照升序或者降序進行排列的數據結構[2].在排序問題中，堆這種數據結構具有很好的效率和更低的時間復雜度.而堆這樣的特性，剛好滿足了Dijkstra 算法求解“最短路徑”，因此，如果使用最小二叉堆這種數據結構來優化Dijkstra 算法，將會大大降低算法的時間復雜度[3].最短路徑問題一直是地理信息科學、計算機信息科學和算法等領域研究中的一個熱點話題[4].近年來，伴隨著網絡數據的井噴，最短路徑問題的實時或近實時計算面臨著新一輪的挑戰[5].Dijkstra 算法有較大的改進空間.

最短路徑問題是一個傳統的數學問題，它的研究一直是地理信息科學和GIS 空間分析的熱門話題，尤其是在資源分配、路線分析和設計等方向發揮著不可提到的作用[6-8].近年來，Dijkstra 算法已廣泛應用于許多領域，如優化，圖像處理和網格處理[9].隨著交通和物流行業的快速發展變革，對Dijkstra 算法的高效運行提出了新的時代要求，關于求解最短路徑問題的算法優化也一直是專家和學者的研究熱點.如：劉剛等[9]從路徑冗余角度研究了傳統Dijkstra 算法中的“交會路徑”和“循環路徑”問題，并針對上述問題提出了一種Dijkstra 算法改進方法.李鑫等[10]把Dijkstra 算法用于動態垃圾量的環衛車系統調度系統研究中，提出了帶反饋機制的環衛車系統調度算法，該算法能有效提高環衛車運行效率，便于垃圾管理.宋青和汪小帆[11]認為最短路徑的快速有效計算研究具有重要的實際意義，以優先隊列為代表的基本加速技術、目標引導技術以及分層技術3 個方面進行了論述.

Sembiring 等人[12]將“該算法用于查找到達最終目的地的路線，找到最短路線，然后消除符合交通堵塞的路線，結果是有效路線，該路線具有可能的最短路線并且沒有交通擁堵點”；Singh 等人[13]在對科學和工業應用的海洋測量和勘探中，研究利用原始生成的網格圖并使用Dijkstra 算法來找到單個USV 的最短路徑，對海洋車輛進行最佳的路線選擇；Tamatjita 和Mahastama[14]在研究以最小的成本或時間選擇最可行的路線，使用Dijkstra 算法在表示具有兩種可能的有向圖的街道路線的圖上應用了該案例：單向和雙向.每個成本都可以隨時更改，代表交通狀況的變化.結果表明，使用單向有向圖繪制路徑確實可以達到目標，而雙向有向圖的使用可能會引起混淆，盡管它可能是現實世界中可能的選擇.兩個實驗都表明，在中途到達目標的同時重新計算最短路徑時沒有額外的計算壓力.

2 Dijkstra 及二叉堆算法理論

2.1 Dijkstra 算法原理

Dijkstra 算法解決的問題是：在一個包含n個節點和m條帶權有向弧組成的有向圖G 中，源點是V0，限定各邊上的權值大于或等于0[13,14].分別求出從源點V0到有向圖G 中其余各頂點的最優路徑.

例如，圖1 所示的帶權有向圖G 中，從源點V0出發，到達其余各個節點，它的最短路徑如表1 所示，從圖1 中可以看到，從V0到V5有4 種不一樣的走法：也就是(V0,V5),(V0,V3,V5),(V0,V2,V4,V5)和(V0,V3,V4,V5),(V0,V5)的長度為1000，(V0,V3,V5)長度卻是900，(V0,V2,V4,V5)也是900，而(V0,V3,V4,V5)是600.顯然(V0,V3,V4,V5)是V0出發到V5的最短路徑；而從V0到V2只有一條路徑(V0,V2)可以到達，距離是100；從V0到V1則沒有路徑可以到達，各個節點的路徑和距離信息如表1 所示.

表1 有向圖G 中從V0 到其余各點的最短路徑

圖1 帶權有向圖G

在實現Dijkstra 算法的過程中，需要有存圖結構-鄰接矩陣，儲存每個點到起點的距離、S 數組，記錄每個點是否被選擇過作為基點、Pre 數組，表示到達這個節點的前一個節點，可以用于最短路徑線路的表示.

2.2 二叉堆算法原理

二叉堆，如其名字一樣，和二叉樹具有緊密的關系.二叉堆是一種特殊的二叉樹，是對一般的二叉樹提出了結構性和堆序性的要求，這種特殊結構性和堆序性是二叉堆的性質所在.一種較為理想的二叉堆表示方法就是使用數組來表示二叉堆，因為使用數組來存儲二叉堆不會浪費存儲空間，如圖2 所示.

圖2 最小二叉堆結構

3 基于二叉堆的Dijkstra 算法設計

在圖3 中，共有8 個節點，16 條邊.假設A是源點，接下來，分別使用不同的算法求解最短路徑，分析和體會兩種算法的時間復雜度的差.

圖3 由節點和有向弧組成的圖G

使用鄰接矩陣存儲數據，格式如下：{{0,20,∞,80,∞,∞,90,∞}, {∞,0,∞,∞,∞,10,∞,∞}, {∞,∞,0,10,∞,50,∞,20}, {∞,∞,10,0,∞,∞,20,28}, {80,50,∞,28,0,∞,30,∞},{50,∞,10,40,∞,0,∞,∞},{20,∞,∞,∞,∞,∞,0,∞},{∞,∞,∞,∞,∞,∞,∞,0}}.

在優化的Dijkstra 算法里定義一個結構變量：Struct node{num; dis; pos; vis; pre}，其中num 域代表節點的序號；dis[i]表示當前找到的從源點A到終點的最短路徑的長度，初始狀態下，dis[i] =G[A][i]，即鄰接矩陣的第1 行；pos 域記錄該節點在堆中的位置；vis 域是布爾型數據，為0 表示該頂點還未加入到集合S 中，vis[i]為1 表示頂點已經加入到集合S 中.初始狀態下，vis[A]為1，其余都為0，表示最初集合S 中只有頂點A；pre 域代表的在最短路徑上的該節點的前一個節點，用于生成最短路徑.初始化結果如表2 所示.

表2 有向圖G 中從V0 到其余各點的最短路徑

第1 步 置源點A的vis[]為true，以源點A的dis[i]為元素，其中dis[i]=arcs[A][i]，對于每一個dis[i]，如果dis[i]/=∞，就將其插入最小二叉堆.建立的最小二叉堆如下圖.置B, D, G的vis 域為1；pre 域=A.結果如表3 和圖4 所示.

圖4 Dijkstra 算法的二叉堆優化存儲示意圖

表3 有向圖G 中從V0 到其余各點的最短路徑

第2 步 建立后的最小堆的堆頂節點為B，即B為離A最近的節點，將B從堆中刪除，并加入集合S 中作為中間節點，對于每一個arcs[B][i]/=∞，如果dis[B] +arcs[B][i]＜dis[i]，則令dis[i] = dis[B]+arcs[B][i].將新更新的點i插入進二叉堆，并更新堆.

與B相鄰接的屬于集合T中的節點，圖中為F節點.因為A通過B到達F的距離為30＜∞，令dis[F] = 30，pre[F]域為B，vis[B] = 1，并將F節點插入二叉堆，并更新堆，結果如表4 和圖5(a)所示.

表4 有向圖G 中從V0 到其余各點的最短路徑

第3 步 此時堆頂元素是F，將F從二叉堆刪除.從F出發共有3 條邊，分別到A, C, D，由于A點的最短路徑已經確定，D點也已經加入二叉堆，所以判斷dis[F]+arcs[F][i]＜dis[i]，則令dis[i]=dis[F]+arcs[F][i].使用40 更新dis[D]，而后將dis[C]=40，放到堆頂，調整二叉堆，結果如表5 和圖5(b)所示.

表5 有向圖G 中從V0 到其余各點的最短路徑

第4 步 此時堆頂元素是C，將C從二叉堆刪除.從F出發共有3 條邊，分別到F, H, D，由于F點的最短路徑已經確定，D點也已經加入二叉堆，所以判斷dis[C]+arcs[C][i]＜dis[i]是否成立，若成立，則令dis[i] = dis[F] + arcs[F][i]，使用50 更新dis[D]，將dis[H] = 60 放到堆頂，然后調整二叉堆，所得結果如表6、圖5(c)和圖5(d)所示.

表6 有向圖G 中從V0 到其余各點的最短路徑

第5 步 此時堆頂元素是D，將D從二叉堆刪除.從F出發共有3 條邊到C, G, H，由于C點的最短路徑已經確定，H點也已經加入二叉堆，所以判斷dis[D]+arcs[D][i]＜dis[i]是否成立，若成立，則令dis[i] = dis[D]+arcs[D][i]，經過D點到達H點的距離是68＞dis[H] = 60，不進行更新，使用70 更新dis[G]，然后調整二叉堆，結果如表7、圖5(e)和圖5(f)所示.

圖5 算法求解過程中二叉堆調整

表7 有向圖G 中從V0 到其余各點的最短路徑

第6 步 此時堆頂元素是H，將H從二叉堆刪除.從H出發無邊，不進行更新和插入操作，如表8 所示.

表8 有向圖G 中從V0 到其余各點的最短路徑

第7 步 此時堆頂元素是G，將G從二叉堆刪除.從G出發只有一條邊，到達A，A點的最短路徑已經確定，不進行操作，此時二叉堆為空，所有從A出發可以到達的節點的最短路徑均已求出，而集合T中還剩下一個E點，因為沒有從其他節點到E節點的有向弧，即E的入度為0，所以無法從源點A到達E點，即最短路徑為∞，算法結束，結果如表9 和表10 所示.

表9 有向圖G 中從V0 到其余各點的最短路徑

表10 算法執行結束后各個數組存儲的信息

優化算法的改進有如下優點：

1) 更新T中的節點距離，只需要對剛加入集合S 的節點所相連接的節點進行比較更新操作即可，對已經產生最短路徑的節點也不再進行更新；

2) 選取離源點距離最短的T中的節點，具有最短距離的節點就是堆頂元素，無需進行比較；

3) 節點的上浮或者下滲操作最多執行n-1 次，所以共有n-1 次刪除操作.

4 實驗及結果分析

4.1 實驗數據設計

由于Dijkstra 算法解決的是實際問題，所以在數據設計上，從實際出發，選取中國的省會城市作為節點，如果兩個省會城市之間火車可以直達，則定義這兩個節點之間存在邊，城市之間的距離為邊的權重.在中國共有34 個省級行政單位，但是，香港、澳門和臺灣三地沒有火車，所以選取另外31 個省會城市作為實驗數據來源.

對原始的距離數據進行處理，以方便程序使用：

1) 如果兩個城市之間存在直達的火車，將火車的可達性定義為1，否則為0.特別地，將A城市到A城市的可達性定義為0；

2) 將城市之間的實際距離數據和火車可達性數據進行柵格相乘，可以得到中國省會城市之間火車是否可以直達以及其實際距離，其中值為0 表示兩個城市之間無直達火車，使用noPath 替換所有0 值，值為其他代表直達火車的實際距離.這里為了方便計算和存儲，統一采用km 作為單位，省略小數點后面的數字；

3) 為了比較不同算法的時間復雜度隨著問題規模的變化，分別取n為8、16 和31.分別在實驗數據中篩選出8 城市、16 個城市的距離數據；

4) 為了比較n一定時，邊數m對算法復雜度的影響，對數據做如下處理：當n取31 時，省會城市之間的實際邊數為813；當限制省會城市之間的距離在800 km 以內時，邊數為233.經過對數據的處理，得到n和m分別為以下數值的實驗數據，共4 組，如表11 所示.

表11 實驗數據中有向圖節點個數n 和邊數m

4.2 傳統算法

受計算機性能的影響，同一個程序同一組數據的執行時間不一樣，所以為了更大程度上屏蔽計算機硬件帶來的影響，盡可能的提高算法求解問題時間的計算精度，所以反復執行程序5 次，然后求其平均數，將其作為程序的執行時間.程序運行結果如表12 所示.

表12 傳統算法求解問題所花費的時間及其平均值

4.3 二叉堆優化算法

仍然使用上面的實驗數據，反復運行二叉堆優化過后的程序，得到算法的基本操作次數和執行時間，如表13 所示.

表13 二叉堆優化的算法求解問題所花費的時間及其平均值

4.4 實驗結果

為了方便對比兩種方法的時間復雜度，將算法的執行時間和次數繪制成圖，如圖6 和圖7 所示.

通過對圖6 和圖7 的觀察，可以發現：使用二叉堆作為數據結構的Dijkstra 算法，它的時間復雜度比傳統的算法低.而且隨著數據量的增大，二叉堆優化的Dijkstra 算法的效率將越來越高.

圖6 不同算法的執行時間對比圖

圖7 不同算法的基本操作執行次數對比圖

5 總結

使用二叉堆作為數據結構的Dijkstra 算法，在數據相同的情況下，它求解問題的時間和基本操作的執行次數要比傳統的Dijkstra 算法少.隨著問題規模n的增大，二叉堆優化的Dijkstra 算法的效率將越來越高.

當節點數量一定時，隨著有向圖中邊的數量不斷增大并逼近最大值n(n-1)，傳統算法的時間復雜度沒有太大變化，而二叉堆優化的算法的時間復雜度會增高，并接近于普通算法的時間復雜度，算法優化的效果不明顯.這是因為當邊數m不斷增加時，從最初的最小二叉堆的建立，到之后的每次刪除和調整等相關操作的時間復雜度都會上升.