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

作者简介:

通讯作者:

中图分类号:

TP303

基金项目:

国家自然科学基金(62372202, 62461160333)


Fully Dynamic Single-source Shortest Paths Algorithm Based on Massively Parallel Model
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    研究大规模并行计算模型中动态单源最短路径问题. 在该模型中, 每台机器内存大小为$ \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) $轮数复杂度的并行静态单源最短路径算法, 所提并行动态精确单源最短路径算法显著降低了轮数复杂度.

    Abstract:

    The dynamic single-source shortest paths problem is studied in the massively parallel computation (MPC) model, where the memory size of each machine is $ \mathrm{O}({n}^{\alpha }) $. Here, $ n $ is the number of vertices in the graph, and $ \alpha \in (0, 1) $ is a constant. This study primarily considers directed or undirected graphs with integer edge weights, where the ratio between the maximum and minimum edge weights is upper-bounded by $ \left\lceil poly(\log n)\right\rceil $. The graph update operations include single-edge insertion, deletion, and weight change. To address this problem, this study combines the polynomial matrix inverse method, the path decomposition strategy, and parallel linear algebra algorithms. In addition, by designing an efficient parallel polynomial multiplication algorithm, a randomized parallel dynamic single-source shortest paths algorithm is proposed. The algorithm achieves an update round complexity of $ \mathrm{O}({\alpha }^{-1}\log n) $ and a total memory requirement of $ \tilde{\mathrm{O}}({n}^{3-3(3-\omega )/(4-\alpha /2)-\alpha (\omega /2-1)}) $. Here, the update round complexity refers to the number of synchronous iteration rounds required by the algorithm to recompute, after each edge change in the graph, the distances from the source to other affected vertices. $ \tilde{\mathrm{O}}(\cdot ) $ suppresses polylogarithmic factors, and $ \omega $ represents the exponent of the arithmetic complexity of fast matrix multiplication on matrices of size $ \mathrm{O}({n}^{\alpha }) $. Compared with existing parallel static single-source shortest paths algorithms that require at least $ poly(\log n) $ round complexity, the proposed algorithm significantly reduces the round complexity.

    参考文献
    相似文献
    引证文献
引用本文

王迟蕾,华强胜,金海.基于大规模并行模型的完全动态单源最短路径算法.软件学报,,():1-19

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2024-08-08
  • 最后修改日期:2026-04-03
  • 录用日期:
  • 在线发布日期: 2026-08-12
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号