一種基于二叉堆的Dijkstra 最短路徑優(yōu)化方法

王芝麟, 喬新輝, 馬 旭, 嚴(yán) 研

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

1 引言

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

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

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

2 Dijkstra 及二叉堆算法理論

2.1 Dijkstra 算法原理

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

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

表1 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

圖1 帶權(quán)有向圖G

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

2.2 二叉堆算法原理

二叉堆，如其名字一樣，和二叉樹具有緊密的關(guān)系.二叉堆是一種特殊的二叉樹，是對(duì)一般的二叉樹提出了結(jié)構(gòu)性和堆序性的要求，這種特殊結(jié)構(gòu)性和堆序性是二叉堆的性質(zhì)所在.一種較為理想的二叉堆表示方法就是使用數(shù)組來表示二叉堆，因?yàn)槭褂脭?shù)組來存儲(chǔ)二叉堆不會(huì)浪費(fèi)存儲(chǔ)空間，如圖2 所示.

圖2 最小二叉堆結(jié)構(gòu)

3 基于二叉堆的Dijkstra 算法設(shè)計(jì)

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

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

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

表2 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

圖4 Dijkstra 算法的二叉堆優(yōu)化存儲(chǔ)示意圖

表3 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

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

表4 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

表5 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

表6 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

圖5 算法求解過程中二叉堆調(diào)整

表7 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

表8 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

表9 有向圖G 中從V0 到其余各點(diǎn)的最短路徑

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

優(yōu)化算法的改進(jìn)有如下優(yōu)點(diǎn)：

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

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

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

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)設(shè)計(jì)

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

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

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

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

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

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

表11 實(shí)驗(yàn)數(shù)據(jù)中有向圖節(jié)點(diǎn)個(gè)數(shù)n 和邊數(shù)m

4.2 傳統(tǒng)算法

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

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

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

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

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

4.4 實(shí)驗(yàn)結(jié)果

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

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

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

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

5 總結(jié)

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

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