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

Clc Number:

TP303

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 08,2024
  • Revised:April 03,2026
  • Adopted:
  • Online: August 12,2026
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063