Sequential Johnson’s APSP Algorithm on GPU
Keywords:
All-Pair Shortest Path, Compute Unified Device Architecture (CUDA), Graphical Processing Unit (GPU)Abstract
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.
Downloads
Published
Issue
Section
License
Copyright (c) 2021 Journal of Computational Learning Strategies & Practices
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
The journal is open access. Reading, downloading, copying, distributing and use of any material for academic and research purposes is free. The copyright in the Journal is owned by the CLSP. Unauthorized copying or redistribution for any financial or earning purpose will be violation of copyright laws. Moreover, managing editor is not responsible for originality of the articles accepted for the journal. However, the authors would be accountable if the ideas and the materials are found plagiarized. The journal is in the process of licensing under a Creative Commons Attribution- Non Commercial 4.0 International License. All articles published by JCLSP will be licensed under the Creative Commons Attribution 4.0 International License. This permits anyone to copy, redistribute, transmit and adapt the work provided the original work and source is appropriately cited as specified by the Creative Commons Attribution License.
