Abstract.

The use of Johnson’s algorithm for finding the shortest path for all pairs of weighted directed graph nodes is proposed. Its formalization in terms of Glushkov’s modified systems of algorithmic algebras is realized. The expediency of GPGPU technology using to accelerate the algorithm is proved. A number of schemas of parallel algorithm optimized for using in GPGPU are obtained. Approach to the implementation of the schemes obtained with the use of computing architecture NVIDIA CUDA is proposed. An experimental study of improved performance by using GPU for computations is realized.

Keywords:

NVIDIA CUDA, GPGPU, SSSP, APSP, Thrust, SAA Scheme, Johnson’s Algorithm.