A Novel Faster All-Pair Shortest Path Algorithm Based on the Matrix Multiplication for GPUs

The shortest path problem is a class of typical problems in graph theory and network science, with a wide range of application scenarios. The state of the art all-pair shortest path algorithm is implemented by the parallel single source shortest path algorithms, since the Floyd algorithm is difficult to accelerate by parallelism. We propose a novel all-pair shortest path algorithm based on block matrix multiplication via GPUs, which transforms shortest path problems into the linear algebra problems and takes advantage of the GPUs' superior performance in this regard. In the experiments, the novel algorithm achieves average of 41.257$\times$ and the maximum of 89.919$\times$ over widely used Dijkstra algorithm which implements the priority queue by the binary heap and is optimized via multi-threading.