A Novel Work-Efficient APSP Algorithm for GPUs

The shortest path problem is a class of classical problems in graph theory and 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 problem. We propose a new all-pair shortest path algorithm based on block matrix multiplication via GPUs. The novel algorithm transforms the shortest path problem into the linear algebra problem, taking advantage of the GPUs' performance advantage in this regard. On sparse graphs, the new algorithm has an average of 2.35x compared to the parallel Dijsktra algorithm and an average of 1500x on the dense graphs.