Implementation of K-shortest Path Algorithm in GPU Using CUDA

Avadhesh Pratap Singh, Dhirendra Pratap Singh
M. Tech Scholar, MANIT Bhoapl, MP, India
Procedia Computer Science, Volume 48, Pages 5-13, 2015


   title={Implementation of K-shortest Path Algorithm in GPU Using CUDA},

   author={Singh, Avadhesh Pratap and Singh, Dhirendra Pratap},

   journal={Procedia Computer Science},






Download Download (PDF)   View View   Source Source   



K-shortest path algorithm is generalization of the shortest path algorithm. K-shortest path is used in various fields like sequence alignment problem in molecular bioinformatics, robot motion planning, path finding in gene network where speed to calculate paths plays a vital role. Parallel implementation is one of the best ways to fulfill the requirement of these applications. A GPU based parallel algorithm is developed to find k number of shortest path in a positive edge-weighted directed large graph. In calculated shortest path repetition of the vertices is not allowed. Implemented algorithm calculates a k-shortest path between two pair of vertices of a graph with n nodes and m vertices. This approach is based on Yen’s algorithm to find k-shortest loopless path. We implemented our algorithms in Nvidia’s GPU using Compute Unified Device Architecture (CUDA). This paper presents comparative analysis between CPU and GPU based implementation of Yen’s Algorithm. Our approach achieves the 6 time speed up in comparison of serial algorithm.
Rating: 0.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: