孙文彬，谭正龙，王江，周长江，何俊芳

（中国矿业大学（北京）地球科学与测绘工程学院，北京 100083）

0 引言

最短路径问题一直是地理信息科学、计算机科学、运筹学、交通运输等领域的一个研究热点［1－3］。许多实际问题都可以抽象为网络最短路径计算问题［3］，如出行路线规划、管网优化等。因此，最短路径算法及优化方法的研究具有重要的实用价值。近年来，国内外学者对最短路径算法进行了较为深入的研究［1－15］，并取得了较好的效果。从近期研究成果看，最短路径算法主要可分为标号设定法和标号修正法两大类。其中，Dijkstra算法为最经典的最短路径算法，当采用Fibonacci堆实现Dijkstra算法时，其时间复杂度可降为O（m＋nlogn）［3］。但将最短路径算法应用到复杂网络问题求解时，如网络流优化、资源分配等，仍存在着计算效率低的缺陷［4，5］。例如，在一台 CPU 2.1GHz，内存512M的联想PC机上，采用串行Dijkstra算法求解包含4 525个结点的西安市交通网络电子地图，当源点数为32时，运行时间为26 437s［4，5］。因此，提高最短路径算法的效率仍然是地理信息科学研究的热点问题之一。

目前，串行的最短路径算法研究已较为成熟，算法的效率几乎达到了理论上的极限值。而串行算法的并行化是提高算法运行效率的有效方法之一［3－15］。卢照等针对单源多汇的路径问题，通过网络节点的分割设计实现了基于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 算法、启发式算法（如A＊算法等）、动态规划、智能算法（如遗传算法、蚁群算法等）及各种加速算法等。其中，基于Fibonacci堆的Dijkstra算法运行效率较高，是求解最短路径问题的主要算法之一。为此，本文将Dijkstra算法作为并行化的基础算法。

通常，串行算法并行化的思路主要有两种模式：任务分割和数据分割。任务分割模式是将算法的实现过程分解成若干个子任务，把各子任务交于不同的进程进行计算处理，再利用MPI通讯将各进程的计算结果进行汇总处理，获取最终结果。当算法各计算步骤之间的关联度低时，可采用任务分割的模式将串行算法并行化。而Dijkstra算法是一个迭代过程，各部分间的关联度高。该算法需要根据设定的标准不断重复节点选择、节点松弛、终止条件判定的操作。Dijkstra算法不宜采用任务分割的方式进行并行化。数据分割是串行算法并行化的另一种主要方式。数据分割是将数据集拆分成若干个子集合，将各子集合数据交给不同的进程进行处理，各进程的计算结果再汇总到同一进程，获取最终的结果。数据分割模式是通过减少各进程计算处理的数据量来提高算法运行效率。现有的最短路径并行算法多采用数据分割的模式。

1.1 基于Boost库的并行算法

Boost库是一种开源的图形图像库，并提供了并行的Boost图形库（Parallel Boost Graph Library，PBGL）。PBGL设计了分布式数据结构和通信机制，以方便网络点、边的分布式存贮，提供了数据和算法进行信息交换的并行通讯进程组，方便用户进行并行程序的设计与开发。PBGL库提供了3种最短路径并行算法：Dijkstra算法、Crauser算法、Δ－stepping算法。

经笔者测试，PBGL提供的最短路径算法的并行效率低，最坏情况时，算法计算耗时甚至大于串行算法。经笔者分析，PBGL的最短路径并行算法节省了计算时间，但增加了大量的MPI通讯，通讯时间开销大，这导致极端情况下并行算法耗时反而会多于串行算法。

1.2 网络分割的并行算法

数据分割是网络分析算法并行化的主要策略之一。而分割方法的选择是影响网络分析算法并行效率的主要因素之一。为了保证算法并行化的效率，网络数据分割需要保证以下两点：1）尽量减少子网络间割点数目，以减少不同进程间的通讯；2）尽量保证各子网络的计算负载均衡。目前，主要的网络数据分割方法包括：坐标嵌套划分、递归惯性二分法、层次嵌套划分、KL／FM方法、模拟退化划分法、条带划分法等。由于Dijkstra算法是一个寻找全局最优的算法，为此，本文将条带划分法作为网络分割的基本方法。条带划分可以降低各部分的关联性，能有效减少MPI的通讯次数，提高算法的并行效率。

条带划分法属于点割集的划分模式。如图1所示，假设求点A到点B的最短路径，以A、B连线方向作为轴，与该轴垂直的方向做割线；依此作P－1条割线将整个网络分成P个割集（子网络），其中，第1个子网络包含点A，最后一个子网络包括点B。在完成网络分割后，可将各条带的网络数据发送给各进程，分别在各进程内计算最短路径。以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

由算法实现的过程可知，网络数据分割能减少各进程内参与运算的节点数和边数，从而达到提高算法运行效率的目的；但同时增加了MPI通讯时间和结果归并时间。此外，首尾两端的进程只需运行一次串行Dijkstra算法，而中间进程需根据割点的数目运行多次Dijkstra算法，容易导致中间进程计算耗时长，进而影响算法的整体效率。笔者利用DIMAS提供的美国东部路网数据（DIMAS－E）进行了实验。在路网数据的两端各选择一个节点，求它们之间的最短路径；作两条割线将整个路网分成三部分，其中位于割线上的割点数为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最短路径算法的搜索是单方向的，算法运行时间取决于搜索过程中所遍历的节点数目。如图2所示，求源点到终点的最短路径时，算法搜索的空间为以源点到终点为半径的圆面，会遍历搜索空间中的所有节点。而对向搜索技术是一种缩小Dijkstra算法搜索空间的方法。采用对向搜索时，算法搜索空间为以源点、终点为圆心，以源点和终点距离1／2为半径的圆面（图3）。从理论上讲，双向搜索可将算法搜索空间缩小为原来的1／2。

在对向搜索中，分别从源点和终点开始的搜索过程是相互独立的。为此，可开辟两个进程，分别从源点和终点为起点运行Dijkstra算法。当两个进程中出现同一个永久标号的节点时，停止搜索；两个进程中求出起（终）点到永久标号节点的路径集合为最终的最短路径。采用双向搜索技术无需对网络数据进行分割，也避免了数据归并处理的过程，可以减少算法的运行时间。

图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）等。其中，弧段标识技术能大量减少最短路径遍历的节点数［14，15］，是求解最短路径问题的有效方法之一。为此，笔者以该技术为例，说明加速方法与并行技术结合的过程。该算法的思路是将整个路网区域按一定的划分规则进行分区，将跨越区域边界的节点作为边缘节点；选择任意一弧段，分别求该弧段两端点到其它区域边缘节点的最短路径；判断获得的最短路径是否经过该弧段，并用相应的标识符进行标注；在最短路径的解算中，根据标识符判定对应弧段是否参与最短路径的求解；通过减少参与运算的弧段数达到提高计算效率的目的。尽管弧段标识技术非常高效，但该技术预处理过程非常耗时。每个弧段标识的建立都需要运行一次Dijkstra算法，当网络的弧段达到数以百万计时，采用串行的方法建立Arc－Flag几乎是不可能完成的任务。因此，将并行技术和Arc－Flag结合是必然。可根据Johson算法原理，通过并行算法建立弧段标识，从而达到减少预处理时间的目的。

3 结论

本文针对单源单汇的最短路径问题，在分析串行算法并行化方法优缺点的基础上，研究了基于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.