Sequential Johnson’s APSP Algorithm on GPU


  • Anila Batool Govt Degree College of Special Education, Sargodha
  • Muntazir Mehdi Superior Group of Colleges, Mianwali


All-Pair Shortest Path, Compute Unified Device Architecture (CUDA), Graphical Processing Unit (GPU)


A quite ordinary issue while processing graphs is to find the shortest distance from one node to all the other nodes. It is called all-pairs shortest path. The applications of finding shortest paths are several including Digital Mapping, Social Networking, Telephone Networks, IP Routing, Fighting Agenda, Robotic Path and many more. Although a lot of work has already been carried out in this aspect but it has been observed that it is quite difficult to exquisitely process graphs which contain a very larger number of nodes. This paper aims to provide a pertinent solution to this problem by proposing three different versions of Johnson’s shortest path solution in parallel architecture over Graphic Processing Unit which resolves APSP problem. As compared to processing extensively large graphs on CPU, proposed architecture will provide a 4.5 time efficient solution for APSP problem.