A multi-source label-correcting algorithm for the all-pairs shortest paths problem

摘要

The All-Pairs Shortest Paths (APSP) problem seeks the shortest path distances between all pairs of vertices, and is one of the most fundamental graph problems. In this paper, a fast algorithm with a small working space for the APSP problem on sparse graphs is presented, which first divides the vertices into sets of vertices with each set having a constant number of vertices and then solves the multi-source shortest paths (MSSP) problem for each set in parallel. For solving the MSSP problems, we give a multi-source label-correcting algorithm, as an extension of a label-correcting algorithm for the single-source shortest path problem. Our algorithm uses fewer operations on the priority queue than an implementation based on Dijkstra's algorithm. Our experiments showed that an implementation of our algorithm with SIMD instructions achieves an order of magnitude speedup for real-world geometric graphs compared to an implementation based on Dijkstra's algorithm.