Abstract: Aiming at the problem that the shortest path algorithm is inefficient in processing large-scale datasets, this paper proposes an all-pairs shortest paths parallel algorithm based on Graphics Processing Unit (GPU) acceleration. Firstly, the optimized matrix multiplication algorithm is used to realize the parallel computing data inter-workgroup and intra-workgroup. Then the branch of work-items caused by irregular rows is reduced. Finally, the access delay of work-items to the strip storage resources of adjacency matrix calculation is reduced. The experimental results show that compared with the performance of the serial algorithm based on AMD Ryzen5 1600X CPU, parallel algorithm based on Open Multi-Processing (OpenMP) and parallel algorithm based on Compute Unified Device Architecture (CUDA), the shortest path parallel algorithm obtains 196.35, 36.76 and 2.25 times speedup in the NVIDIA GeForce GTX 1070 computing platform under the Open Computing Language (OpenCL) architecture respectively. The validity and performance portability of the proposed parallel optimization method are verified.