The computation of the all-pairs shortest paths is an important graph algorithmic problem. When the graph changes, such as edge deletions/insertions, recalculating the shortest distance of a graph from scratch is costly. In this paper, we investigate how to quickly maintain the shortest distance of the dynamic graph in the distributed memory system. For a distributed system with \(p\) processors, the state-of-art algorithm to recompute the shortest distance of a graph with \(n\) vertices from scratch requires \(O\left({n}^{2}/\sqrt{p}\right)\) bandwidth cost and \(O\left(\sqrt{p}{\text{log}}^{2}p\right)\) latency cost. For the insertion of \(k\) edges, we give an incremental algorithm with a bandwidth cost of \(O\left(\frac{nk}{\sqrt{p}}+{k}^{2}\right)\) and a latency cost of \(O\left(\text{log}p\right)\) . For typical scenarios where \(k=O\left(\frac{n}{\sqrt{p}}\right)\) , the bandwidth and latency costs are reduced by a factor of \(O\left(\sqrt{p}\right)\) and \(O\left(\sqrt{p}\text{log}p\right)\) , respectively. For the deletion of \(k\) edges, we give a decremental algorithm with a bandwidth cost of \(O\left(\frac{nk}{\sqrt{p}}+{k}^{2}+\frac{{n}^{2}}{p}{\text{log}}^{3}p+{\left|S\right|}^{2}\text{log}p\right)\) and a latency cost of \(O\left({\text{log}}^{3}p\right)\) , where \(\left|S\right|\) is the separator size of a constructed graph and is related to the alteration degree of the shortest path of the dynamic graph. When \(k=O\left(\frac{n}{\sqrt{p}}\right)\) and \(\left|S\right|=O\left(\frac{n}{\sqrt{p}}\right)\) , the bandwidth and latency costs are reduced by a factor of \(O\left(\sqrt{p}/{\text{log}}^{3}p\right)\) and \(O\left(\sqrt{p}/\text{log}p\right)\) , respectively.
