GPU-Based Hybrid Algorithm of All-pairs Shortest Paths

As an essential graph algorithmic pattern, the All-Pairs Shortest Paths Problem (APSP) plays an important role in many crucial applications such as bioinformatics, geographic information systems, social networks, complex network analysis, computer-aided design of integrated circuits and transportation planning. Due to the significant divergence of graphs, this work investigates GPU-based APSP parallel algorithms that adapt to varying graph structures. First, we propose an improved vertex-parallel algorithm, so-called optimized vertex-parallel algorithm, which performs best on graphs with a large diameter. Second, we proposed a hybrid algorithm integrating the optimized vertex-parallel algorithm vertex- and an edge-parallel algorithm that can efficiently handle graphs with arbitrary structure. Finally, we proposed a sampling heuristic to further improve the performance of the hybrid algorithm. Experimental results prove that the sampling hybrid algorithm achieves a speedup of up to 7.2×on high-diameter graphs and 1.9×on other graphs. The sampling hybrid algorithm also has a better scalability on large graphs.