软件学报:jos:7706 · 记录 #1

基于大规模并行模型的完全动态单源最短路径算法

来源日期 2026-08-12

来源记录日期 2026-08-12

雷达观测 2026-11-05 00:19

摘要

研究大规模并行计算模型中动态单源最短路径问题. 在该模型中, 每台机器内存大小为$ \mathrm{O}({n}^{\alpha }) $, $ n $表示图中顶点数, $ \alpha \in (0, 1) $是一个常数. 主要考虑带整数边权重的有向或无向图, 其中边权重最大值与最小值之比的上限为$ \left\lceil poly(\log n)\right\rceil $. 图的更新操作包括单边插入、删除以及权重改变. 针对上述问题, 结合多项式矩阵逆方法、路径分解策略以及并行线性代数算法; 同时, 通过设计一种高效的并行多项式乘法求解算法提出了一个随机并行动态单源最短路径算法. 该算法的更新轮数复杂度为$ \mathrm{O}({\alpha }^{-1}\log n) $, 总内存需求为$ \tilde{\mathrm{O}}({n}^{3-3(3-\omega )/(4-\alpha /2)-\alpha (\omega /2-1)}) $. 其中, 更新轮数复杂度指每次图中边发生变化后, 为重新计算从源点到其他受影响顶点之间的距离, 算法所需同步的迭代轮数; $ \tilde{\mathrm{O}}(\cdot ) $隐去了对数多项式因子, $ \omega $为快速矩阵乘法的算术复杂度($ \mathrm{O}({n}^{\alpha }) $)指数. 相较于现有方法至少需要$ poly(\log n) $轮数复杂度的并行静态单源最短路径算法, 所提并行动态精确单源最短路径算法显著降低了轮数复杂度.