Abstract: In order to improve the computational performance of searching all-pairs shortest paths in a large-scale network， an exact all-pairs shortest path method—RASP algorithm is proposed based on the reoptimization theory. First， the correlation and difference between the shortest path trees with different sources are analyzed. Second， the efficient conversion from a known single-source shortest path tree to another one with different source is achieved based on the reoptimization-based theory. Furthermore， the reoptimization-based all-pairs shortest path (RASP) algorithm utilizes this conversion method to calculate efficiently all-pairs shortest paths. At last， the time complexity of RASP algorithm is proved to be O(3n²+2nm). The experimental test demonstrates that RASP algorithm gains the advantage over Floyd， n-Dijkstra algorithms and their improved algorithms in both sparse and dense networks.

Key words: reoptimization, all-pairs, shortest path, large-scale network, Floyd algorithm, Dijkstra algorithm