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.