A Novel Work-Efficient APSP Algorithm for GPUs

The shortest path problem is a class of typical problems in graph theory and network science, it has a wide range of application scenarios. At present, the parallel single-source shortest path algorithm is mainly used to solve the all-pair shortest path problems. We propose a novel all-pair shortest path algorithm based on block matrix multiplication via GPUs. Our key advancement is transforming the shortest path problems into the linear algebra problems, taking advantage of the GPUs' performance ascendancy in this regard. In the experiments, the novel algorithm achieves average of 41.257$\times$ and the maximum of 89.919$\times$ over Dijkstra algorithm which implements the priority queue by the binary heap and optimized via multi-threaded.