孫文彬，譚正龍，王江，周長江，何俊芳

（中國礦業(yè)大學（北京）地球科學與測繪工程學院，北京 100083）

0 引言

最短路徑問題一直是地理信息科學、計算機科學、運籌學、交通運輸等領域的一個研究熱點［1－3］。許多實際問題都可以抽象為網絡最短路徑計算問題［3］，如出行路線規(guī)劃、管網優(yōu)化等。因此，最短路徑算法及優(yōu)化方法的研究具有重要的實用價值。近年來，國內外學者對最短路徑算法進行了較為深入的研究［1－15］，并取得了較好的效果。從近期研究成果看，最短路徑算法主要可分為標號設定法和標號修正法兩大類。其中，Dijkstra算法為最經典的最短路徑算法，當采用Fibonacci堆實現Dijkstra算法時，其時間復雜度可降為O（m＋nlogn）［3］。但將最短路徑算法應用到復雜網絡問題求解時，如網絡流優(yōu)化、資源分配等，仍存在著計算效率低的缺陷［4，5］。例如，在一臺 CPU 2.1GHz，內存512M的聯(lián)想PC機上，采用串行Dijkstra算法求解包含4 525個結點的西安市交通網絡電子地圖，當源點數為32時，運行時間為26 437s［4，5］。因此，提高最短路徑算法的效率仍然是地理信息科學研究的熱點問題之一。

目前，串行的最短路徑算法研究已較為成熟，算法的效率幾乎達到了理論上的極限值。而串行算法的并行化是提高算法運行效率的有效方法之一［3－15］。盧照等針對單源多匯的路徑問題，通過網絡節(jié)點的分割設計實現了基于MPI的最短路徑搜索算法［4，5］。黃躍峰等借鑒Δ－stepping算法的思想，以多核平臺為基礎，設計了單源多匯的并行最短路徑算法［6］。楊慶芳等探討了基于MPI和OpenMP混合編程模式下的多源多匯并行最短路徑算法［7］。張清華等借助網絡分割的思想，采用點集分割的方式實現了單源多匯的最短路徑并行算法［8］。Nick等基于并行Boost庫完成了并行最短路徑求解［10］。Meyer等以多核服務器平臺為基礎，提出了Δ－stepping的最短路徑并行算法［11］。Kalapana等討論了并行技術與最短路徑加速方法結合的問題［12－15］。但上述研究多是針對多源多匯、單源多匯的最短路徑問題。而在實際應用中，單源單匯是最常見的最短路徑查詢方式，即尋求從一固定初始點到一固定目標點的最短路徑。而將上述的并行算法應用到單源單匯最短路徑問題時，不能保證算法的高效性和普適性。為此，本文擬以MPI為基礎，探討單源單匯最短路徑算法的并行化策略。

1 最短路徑并行算法

常見的最短路徑算法包括：Dijkstra算法、Bellem－ford－Moore（BFM）算法、SPFA 算法、啟發(fā)式算法（如A＊算法等）、動態(tài)規(guī)劃、智能算法（如遺傳算法、蟻群算法等）及各種加速算法等。其中，基于Fibonacci堆的Dijkstra算法運行效率較高，是求解最短路徑問題的主要算法之一。為此，本文將Dijkstra算法作為并行化的基礎算法。

通常，串行算法并行化的思路主要有兩種模式：任務分割和數據分割。任務分割模式是將算法的實現過程分解成若干個子任務，把各子任務交于不同的進程進行計算處理，再利用MPI通訊將各進程的計算結果進行匯總處理，獲取最終結果。當算法各計算步驟之間的關聯(lián)度低時，可采用任務分割的模式將串行算法并行化。而Dijkstra算法是一個迭代過程，各部分間的關聯(lián)度高。該算法需要根據設定的標準不斷重復節(jié)點選擇、節(jié)點松弛、終止條件判定的操作。Dijkstra算法不宜采用任務分割的方式進行并行化。數據分割是串行算法并行化的另一種主要方式。數據分割是將數據集拆分成若干個子集合，將各子集合數據交給不同的進程進行處理，各進程的計算結果再匯總到同一進程，獲取最終的結果。數據分割模式是通過減少各進程計算處理的數據量來提高算法運行效率?，F有的最短路徑并行算法多采用數據分割的模式。

1.1 基于Boost庫的并行算法

Boost庫是一種開源的圖形圖像庫，并提供了并行的Boost圖形庫（Parallel Boost Graph Library，PBGL）。PBGL設計了分布式數據結構和通信機制，以方便網絡點、邊的分布式存貯，提供了數據和算法進行信息交換的并行通訊進程組，方便用戶進行并行程序的設計與開發(fā)。PBGL庫提供了3種最短路徑并行算法：Dijkstra算法、Crauser算法、Δ－stepping算法。

經筆者測試，PBGL提供的最短路徑算法的并行效率低，最壞情況時，算法計算耗時甚至大于串行算法。經筆者分析，PBGL的最短路徑并行算法節(jié)省了計算時間，但增加了大量的MPI通訊，通訊時間開銷大，這導致極端情況下并行算法耗時反而會多于串行算法。

1.2 網絡分割的并行算法

數據分割是網絡分析算法并行化的主要策略之一。而分割方法的選擇是影響網絡分析算法并行效率的主要因素之一。為了保證算法并行化的效率，網絡數據分割需要保證以下兩點：1）盡量減少子網絡間割點數目，以減少不同進程間的通訊；2）盡量保證各子網絡的計算負載均衡。目前，主要的網絡數據分割方法包括：坐標嵌套劃分、遞歸慣性二分法、層次嵌套劃分、KL／FM方法、模擬退化劃分法、條帶劃分法等。由于Dijkstra算法是一個尋找全局最優(yōu)的算法，為此，本文將條帶劃分法作為網絡分割的基本方法。條帶劃分可以降低各部分的關聯(lián)性，能有效減少MPI的通訊次數，提高算法的并行效率。

條帶劃分法屬于點割集的劃分模式。如圖1所示，假設求點A到點B的最短路徑，以A、B連線方向作為軸，與該軸垂直的方向做割線；依此作P－1條割線將整個網絡分成P個割集（子網絡），其中，第1個子網絡包含點A，最后一個子網絡包括點B。在完成網絡分割后，可將各條帶的網絡數據發(fā)送給各進程，分別在各進程內計算最短路徑。以P＝3的情況為例，說明算法的實現步驟：1）如圖1所示，建立兩條割線，第1條割線分別經過點C、D、E，第2條割線經過點F、G、H，分割后形成3個子圖；2）開辟3個進程0、1、2，0號進程運行1次Dijkstra算法，分別計算出A點到割點C、D、E的距離和路徑，分別記為D1、D2、D3及P1、P2、P3；1號進程運行3次Dijkstra算法，分別計算割點C、D、E到割點F、G、H的最短距離和路徑，分別用D4、D5…D12和P4、P5…P12表示；2號進程運行1次Dijkstra算法，計算出B到F、G、H的最短距離和路徑，用D13、D14、D15和P13、P14、P15表示；3）將進程1和進程2中所有距離值和路徑通過MPI廣播的方式傳遞給0號進程；4）在0號進程中，從D1、D2、D3中任取一個路徑，從D4、D5…D12中任取一個路徑，從D13、D14、D15中任取一個，相加得到從A到B的一條路徑；5）重復第4步，求出所有A到B的路徑和距離值，共81條路徑，取其中的最小值，即為A到B的最短距離值，根據編號得到相對應的路徑。

圖1 網絡的條帶分割Fig.1 Strip partition of network

由算法實現的過程可知，網絡數據分割能減少各進程內參與運算的節(jié)點數和邊數，從而達到提高算法運行效率的目的；但同時增加了MPI通訊時間和結果歸并時間。此外，首尾兩端的進程只需運行一次串行Dijkstra算法，而中間進程需根據割點的數目運行多次Dijkstra算法，容易導致中間進程計算耗時長，進而影響算法的整體效率。筆者利用DIMAS提供的美國東部路網數據（DIMAS－E）進行了實驗。在路網數據的兩端各選擇一個節(jié)點，求它們之間的最短路徑；作兩條割線將整個路網分成三部分，其中位于割線上的割點數為50個，實驗結果如表1所示。串行算法運行時間為2.352s。2進程時，進程計算用時分別為1.255s和1.265s，MPI通訊時間分別為0.043s和0.044s。3進程時，首尾進程計算用時分別為0.687s和0.690s；由于存在50個割點，中間進程需運行50次Dijkstra算法，計算用時為29.370s，MPI通訊時間為0.024s；由于采用阻塞式的MPI通訊，1、3號進程需要等2號進程運算完成后才能進行通訊，導致1、3號進程等待通訊及 MPI通訊時間增大，分別為30.410s和30.780s。由此可以看出，2進程時，最短路徑算法的并行效果最佳；將網絡數據分割成多于2個條帶時，中間部分需要多次運行串行算法，反而會造成并行算法整體效率下降。

表1 網絡分割算法的測試結果Table 1 The result of algorithm based on subdividing network

1.3 對向并行算法

Dijkstra最短路徑算法的搜索是單方向的，算法運行時間取決于搜索過程中所遍歷的節(jié)點數目。如圖2所示，求源點到終點的最短路徑時，算法搜索的空間為以源點到終點為半徑的圓面，會遍歷搜索空間中的所有節(jié)點。而對向搜索技術是一種縮小Dijkstra算法搜索空間的方法。采用對向搜索時，算法搜索空間為以源點、終點為圓心，以源點和終點距離1／2為半徑的圓面（圖3）。從理論上講，雙向搜索可將算法搜索空間縮小為原來的1／2。

在對向搜索中，分別從源點和終點開始的搜索過程是相互獨立的。為此，可開辟兩個進程，分別從源點和終點為起點運行Dijkstra算法。當兩個進程中出現同一個永久標號的節(jié)點時，停止搜索；兩個進程中求出起（終）點到永久標號節(jié)點的路徑集合為最終的最短路徑。采用雙向搜索技術無需對網絡數據進行分割，也避免了數據歸并處理的過程，可以減少算法的運行時間。

圖2 Dijkstra算法搜索空間Fig.2 Search range of Dijkstra algorithm

圖3 對向搜索的原理Fig.3 The principle of Bidirectional search

應用 DIMAS（http：／／www.dis.uniroma1.it／challenge9／download.shtml）提供的數據測試了對向并行算法效率（表2）。由表2可知，隨著路徑長度的增加，對向并行算法的計算時間和MPI通訊時間均呈增加的趨勢；對向并行算法的計算用時為串行算法的1／3左右；MPI通訊時間為并行算法計算用時的1／10～1／5，MPI通訊時間遠小于計算用時。因此，并行算法的耗時為串行算法的24.9%～55.8%，均小于串行的Dijkstra算法。

表2 對向搜索算法的測試結果Table 2 The result of Bidirectional search algorithm

2 加速方法與并行策略的結合

最短路徑的加速方法也是近年來研究的重點之一。最短路徑加速方法主要有：引導剪枝（Global－Direction）、弧段標識（Arc－Flag）、幾何容器（Containers）、網絡分層（Multi－Level）等。其中，弧段標識技術能大量減少最短路徑遍歷的節(jié)點數［14，15］，是求解最短路徑問題的有效方法之一。為此，筆者以該技術為例，說明加速方法與并行技術結合的過程。該算法的思路是將整個路網區(qū)域按一定的劃分規(guī)則進行分區(qū)，將跨越區(qū)域邊界的節(jié)點作為邊緣節(jié)點；選擇任意一弧段，分別求該弧段兩端點到其它區(qū)域邊緣節(jié)點的最短路徑；判斷獲得的最短路徑是否經過該弧段，并用相應的標識符進行標注；在最短路徑的解算中，根據標識符判定對應弧段是否參與最短路徑的求解；通過減少參與運算的弧段數達到提高計算效率的目的。盡管弧段標識技術非常高效，但該技術預處理過程非常耗時。每個弧段標識的建立都需要運行一次Dijkstra算法，當網絡的弧段達到數以百萬計時，采用串行的方法建立Arc－Flag幾乎是不可能完成的任務。因此，將并行技術和Arc－Flag結合是必然?？筛鶕﨡ohson算法原理，通過并行算法建立弧段標識，從而達到減少預處理時間的目的。

3 結論

本文針對單源單匯的最短路徑問題，在分析串行算法并行化方法優(yōu)缺點的基礎上，研究了基于Boost庫、網絡分割、對向搜索的Dijkstra算法的并行化策略。應用路網數據進行了測試，結果表明：基于并行Boost庫的最短路徑算法并行效率低；當2進程時，基于網絡條帶分割的最短路徑算法效果最佳；對向搜索的并行算法效率高，算法耗時為串行Dijkstra算法的1／4～1／2。

［1］ BERTSEKAS D P.Network Optimization：Continuous and Discrete［M］.Belmont，MA：Athena Scientific，1998.

［2］ KALPANA R.THAMBIDURAI P.Performance analysis of parallel speedup techniques for shortest path queries in networks of random and planar types［J］.International Journal of Computer Applications.2012，47（24）：29－35.

［3］ 宋青，汪小帆.最短路徑算法加速技術研究綜述［J］.電子科技大學學報，2012，41（2）：176－184.

［4］ 盧照.基于城市路網最短路徑并行搜索算法的研究［D］.陜西師范大學，2011.

［5］ 盧照，師軍.并行最短路徑搜索算法的設計與實現［J］.計算機工程與應用，2010，46（3）：69－71.

［6］ 黃躍峰，鐘耳順.多核平臺并行單源最短路徑算法［J］.計算機工程，2012，38（2）：1－3.

［7］ 楊慶芳，劉冬，楊兆升.基于MPI＋OpenMP混合編程模式的城市路網最短路徑并行算法［J］.吉林大學學報（工學版），2011，41（6）：1581－1584.

［8］ 張清華，李鴻，沈文.基于點割集的并行最短路徑算法［J］.鄭州大學學報（工學版），2012，33（5）：125－129.

［9］ KAMESH M，DAVID A B，JONATHAN W，et al.Parallel Shortest Path Algorithms for Solving Large－Scale Instances［C］.http：／／www.dis.uniroma1.it／challenge9／papers.shtml.2006.1－40.2012－12－31.

［10］ NICK E，ALEX B，DOUGLAS G，et al.Single－source shortest paths with the parallel Boost graph library［C］.http：／／www.dis.uniroma1.it／challenge9／papers.shtml..2006.1－20.2012－12－31.

［11］ MEYER U，SANDERS P.Δ－stepping：A parallelizable shortest path algorithm［J］.Algorithms，2003，49：114－152.

［12］ KALAPANA R，THAMBIDURAI P.Optimizing shortest path queries with parallelized arc flags［A］.Proceedings of IEEE International Conference on Recent Trends in Information Technology［C］.2011.1－6.

［13］ DANIL D，BASTIAN K，THOMAS P.Parallel computation of best connections in public transportation networks［A］.24th International Parallel and Distributed Processing Symposium［C］.IEEE Computer Society，2010.1－12.

［14］ LAUTHER U.An extremely fast，exact algorithm for finding shortest paths in static networks with geographical background［A］.RAUBAL A M.SLIWINSKI W K.GI－Tage 2004［C］.2004，22：219－230.

［15］ LAUTHER U.An experimental evaluation of point－to－point shortest path calculation on road networks with precalculated edgeflags［A］.9th DIMACS Implementation Challenge［C］.http：／／www.dis.uniroma1.it／challenge9／papers.shtml.2006.1－28.2012－12－31.