计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 594-600.doi: 10.11896/jsjkx.210400062
陈钧吾, 余华山
CHEN Jun-wu, YU Hua-shan
摘要: 单源最短路径问题是图算法理论中的经典问题,目的是在带权图上搜索一个源点到其他各个顶点的最短路径。Δ-stepping算法结合了经典Dijkstra算法和Bellman-Ford算法的优势,被广泛用于并行环境的单源最短路径计算。大规模网络的结构按照连接偏好机制演化,其顶点的度数分布呈显著的倾斜特征。基于大规模网络的倾斜性,提出了对Δ-stepping算法的两类改进策略。通过预处理计算任意两个顶点之间的距离上限,实现对边松弛操作的调度优化,提高单源最短路径计算的效率以及在并行环境中的伸缩性。首先,把权重超过所关联顶点之间距离上限值的边标记出来,在单源最短路径计算时,直接跳过这些边,从而减少计算过程中被松弛的边的数量。其次,利用顶点之间距离的上限值动态优化顶点的松弛顺序,只有一个顶点到源点的当前路径的长度不超过它们之间的距离上限值时,才松弛该顶点关联的边,从而减少这些边上的重复松弛操作。测试结果表明,与Graph500实现的Δ-stepping算法相比,改进后的算法在Graph500的基准测试图上有接近10倍的性能提升,在一些真实图上也有2.68~5.58倍的性能提升。
中图分类号:
[1] BERTSEKAS D P.Network Optimization:Continuous and Discrete Models[J].Athena Scientific,1998(9):877-877. [2] AHUJA R K,MAGNANTI T L,ORLIN J B,et al.Networkflows-theory,algorithms and applications[J].Journal of the Operational Research Society,1993,45(11):791-796. [3] MEYER U,SANDERS P.Δ-stepping:A parallel single source shortest path algorithm[C]//Proceedings of Annual European Symposium on Algorithms(Esa'98).1998:393-404. [4] MEYER U,SANDERS P.Δ-stepping:a parallelizable shortestpath algorithm[J].Journal of Algorithms,2003,49(1):114-152. [5] BLELLOCH G E,GU Y,SUN Y,et al.Parallel shortest paths using radius stepping[C]//Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures.2016:443-454. [6] CHAKARAVARTHY V T,CHECCONI F,MURALI P,et al.Scalable single source shortest path algorithms for massively parallel systems[J].IEEE Transactions on Parallel and Distri-buted Systems,2016,28(7):2031-2045. [7] BEAMER S,ASANOVIC K,PATTERSON D.Direction-opti-mizing breadth-first search[C]//Proceedings of the InternationalConference on High Performance Computing,Networking,Storage and Analysis(SC'12).IEEE,2012:1-10. [8] DELLING D,GOLDBERG A V,NOWATZYK A,et al.PHAST:Hardware-accelerated shortest path trees[J].Journal of Parallel and Distributed Computing,2013,73(7):940-952. [9] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world'networks[J].Nature,1998,393(6684):440-442. [10] ALBERT-LASZLO B,ALBERT R.Emergence of Scaling inRandom Networks[J].Science,1999,286(5439):509-512. [11] LESKOVEC J,CHAKRABARTI D,KLEINBERG J,et al.Kronecker graphs:an approach to modeling networks[J].arXiv:0812.4905v2,2009. [12] MURPHY R C.WHEELER K B,BARRETT B W,et al.Introducing the graph 500[J].Cray User Group,2010,19:45-74. [13] UENO K,SUZUMURA T.Highly scalable graph search for the Graph500 benchmark[C]//Proceedings of the 21st International Symposium on High-Performance Parallel and Distributed Computing.ACM,2012:149-160. [14] ALBERT R,BARABÁSIA L.Statistical mechanics of complex networks[J/OL].https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.74.47. |
[1] | 王永, 崔源. 基于四边形最优圈内最短路径的旅行商问题割边方法 Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals 计算机科学, 2022, 49(6A): 199-205. https://doi.org/10.11896/jsjkx.210400065 |
[2] | 鄂海红, 张田宇, 宋美娜. 基于Web的数据可视化图表渲染优化方法 Web-based Data Visualization Chart Rendering Optimization Method 计算机科学, 2021, 48(3): 119-123. https://doi.org/10.11896/jsjkx.200600038 |
[3] | 张晓, 张思蒙, 石佳, 董聪, 李战怀. Ceph分布式存储系统性能优化技术研究综述 Review on Performance Optimization of Ceph Distributed Storage System 计算机科学, 2021, 48(2): 1-12. https://doi.org/10.11896/jsjkx.201000149 |
[4] | 赵晓薇, 朱小军, 韩周卿. 面向定位应用的无人机的悬停位置和飞行路径优化 Hover Location Selection and Flight Path Optimization for UAV for Localization Applications 计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105 |
[5] | 徐江峰谭玉龙. 基于机器学习的HBase配置参数优化研究 Research on HBase Configuration Parameter Optimization Based on Machine Learning 计算机科学, 2020, 47(6A): 474-479. https://doi.org/10.11896/JsJkx.190900046 |
[6] | 周建新, 张志鹏, 周宁. 基于CKSP的分段路由负载均衡技术 Load Balancing Technology of Segment Routing Based on CKSP 计算机科学, 2020, 47(4): 256-261. https://doi.org/10.11896/jsjkx.190500122 |
[7] | 张彭奕, 宋杰. 区块链共识算法效能优化研究进展 Research Advance on Efficiency Optimization of Blockchain Consensus Algorithms 计算机科学, 2020, 47(12): 296-303. https://doi.org/10.11896/jsjkx.200700020 |
[8] | 徐传福,王曦,刘舒,陈世钊,林玉. 基于Python的大规模高性能LBM多相流模拟 Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python 计算机科学, 2020, 47(1): 17-23. https://doi.org/10.11896/jsjkx.190500009 |
[9] | 耿海军, 尹霞. 基于增量最短路径优先的域内高效路由保护算法 Efficient Intra-domain Routing Protection Algorithm Based on i-SPF 计算机科学, 2019, 46(8): 116-120. https://doi.org/10.11896/j.issn.1002-137X.2019.08.019 |
[10] | 何霞, 汤一平, 王丽冉, 陈朋, 袁公萍. 基于Faster RCNNH的多任务分层图像检索技术 Multitask Hierarchical Image Retrieval Technology Based on Faster RCNNH 计算机科学, 2019, 46(3): 303-313. https://doi.org/10.11896/j.issn.1002-137X.2019.03.045 |
[11] | 张凌浩, 桂盛霖, 穆逢君, 王胜. 基于后缀树的二进制可执行代码的克隆检测算法 Clone Detection Algorithm for Binary Executable Code with Suffix Tree 计算机科学, 2019, 46(10): 141-147. https://doi.org/10.11896/jsjkx.180801573 |
[12] | 耿海军. 基于优化链路权值的域内路由保护方案 Intra-domain Routing Protection Scheme by Optimizing Link Weight 计算机科学, 2019, 46(1): 143-147. https://doi.org/10.11896/j.issn.1002-137X.2019.01.022 |
[13] | 徐启泽, 韩文廷, 陈俊仕, 安虹. 众核平台上广度优先搜索算法的优化 Optimization of Breadth-first Search Algorithm Based on Many-core Platform 计算机科学, 2019, 46(1): 314-319. https://doi.org/10.11896/j.issn.1002-137X.2019.01.049 |
[14] | 孙涛, 张俊星. SDN性能优化技术研究综述 Review of SDN Performance Optimization Technology 计算机科学, 2018, 45(11A): 84-91. |
[15] | 满振祯,余世明,何德峰. 基于改进伊藤算法的最短路径网络路由优化算法 Shortest Path Network Routing Optimization Algorithm Based on Improved ITO Algorithm 计算机科学, 2017, 44(7): 215-220. https://doi.org/10.11896/j.issn.1002-137X.2017.07.038 |
|