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

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

1 引言

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

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

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

2 Dijkstra 及二叉堆算法理論

2.1 Dijkstra 算法原理

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

例如，圖1 所示的帶權有向圖G 中，從源點V0出發(fā)，到達其余各個節(jié)點，它的最短路徑如表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出發(fā)到V5的最短路徑；而從V0到V2只有一條路徑(V0,V2)可以到達，距離是100；從V0到V1則沒有路徑可以到達，各個節(jié)點的路徑和距離信息如表1 所示.

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

圖1 帶權有向圖G

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

2.2 二叉堆算法原理

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

圖2 最小二叉堆結構

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

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

圖3 由節(jié)點和有向弧組成的圖G

使用鄰接矩陣存儲數(shù)據(jù)，格式如下：{{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}}.

在優(yōu)化的Dijkstra 算法里定義一個結構變量：Struct node{num; dis; pos; vis; pre}，其中num 域代表節(jié)點的序號；dis[i]表示當前找到的從源點A到終點的最短路徑的長度，初始狀態(tài)下，dis[i] =G[A][i]，即鄰接矩陣的第1 行；pos 域記錄該節(jié)點在堆中的位置；vis 域是布爾型數(shù)據(jù)，為0 表示該頂點還未加入到集合S 中，vis[i]為1 表示頂點已經(jīng)加入到集合S 中.初始狀態(tài)下，vis[A]為1，其余都為0，表示最初集合S 中只有頂點A；pre 域代表的在最短路徑上的該節(jié)點的前一個節(jié)點，用于生成最短路徑.初始化結果如表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 算法的二叉堆優(yōu)化存儲示意圖

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

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

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

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

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

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

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

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

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

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

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

表10 算法執(zhí)行結束后各個數(shù)組存儲的信息

優(yōu)化算法的改進有如下優(yōu)點：

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

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

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

4 實驗及結果分析

4.1 實驗數(shù)據(jù)設計

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

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

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

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

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

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

表11 實驗數(shù)據(jù)中有向圖節(jié)點個數(shù)n 和邊數(shù)m

4.2 傳統(tǒng)算法

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

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

4.3 二叉堆優(yōu)化算法

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

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

4.4 實驗結果

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

通過對圖6 和圖7 的觀察，可以發(fā)現(xiàn)：使用二叉堆作為數(shù)據(jù)結構的Dijkstra 算法，它的時間復雜度比傳統(tǒng)的算法低.而且隨著數(shù)據(jù)量的增大，二叉堆優(yōu)化的Dijkstra 算法的效率將越來越高.

圖6 不同算法的執(zhí)行時間對比圖

圖7 不同算法的基本操作執(zhí)行次數(shù)對比圖

5 總結

使用二叉堆作為數(shù)據(jù)結構的Dijkstra 算法，在數(shù)據(jù)相同的情況下，它求解問題的時間和基本操作的執(zhí)行次數(shù)要比傳統(tǒng)的Dijkstra 算法少.隨著問題規(guī)模n的增大，二叉堆優(yōu)化的Dijkstra 算法的效率將越來越高.

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