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.