面向无尺度图的Δ-stepping算法改进策略

摘要：

单源最短路径问题是图算法理论中的经典问题,目的是在带权图上搜索一个源点到其他各个顶点的最短路径.Δ-stepping算法结合了经典Dijkstra算法和Bellman-Ford算法的优势,被广泛用于并行环境的单源最短路径计算.大规模网络的结构按照连接偏好机制演化,其顶点的度数分布呈显著的倾斜特征.基于大规模网络的倾斜性,提出了对Δ-stepping算法的两类改进策略.通过预处理计算任意两个顶点之间的距离上限,实现对边松弛操作的调度优化,提高单源最短路径计算的效率以及在并行环境中的伸缩性.首先,把权重超过所关联顶点之间距离上限值的边标记出来,在单源最短路径计算时,直接跳过这些边,从而减少计算过程中被松弛的边的数量.其次,利用顶点之间距离的上限值动态优化顶点的松弛顺序,只有一个顶点到源点的当前路径的长度不超过它们之间的距离上限值时,才松弛该顶点关联的边,从而减少这些边上的重复松弛操作.测试结果表明,与Graph500实现的Δ-stepping算法相比,改进后的算法在Graph500的基准测试图上有接近10倍的性能提升,在一些真实图上也有2.68～5.58倍的性能提升.

关键词：最短路径、大规模图、Δ-stepping算法、性能优化

所属期刊栏目：49

分类号：TP311(计算技术、计算机技术)

资助基金：国家重点研发计划2018YFB0204100

在线出版日期：2022-06-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：594-600