Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford

Gaurav Hajela, Manish Pandey
Department of Computer Science and Engineering, Maulana Azad National Institute of Technology, Bhopal, India
International Journal of Computer Applications, Volume 95, No. 15, 2014


   author={Gaurav Hajela and Manish Pandey},

   title={Article: Parallel Implementations for Solving Shortest Path Problem using Bellman-Ford},

   journal={International Journal of Computer Applications},






   note={Published by Foundation of Computer Science, New York, USA}


Download Download (PDF)   View View   Source Source   



In this paper, different parallel implementations of Bellman-Ford algorithm on GPU using OpenCL are presented. These variants include Bellman-Ford for solving single source shortest path (SSSP) having two variants and Bellman-Ford for all pair shortest path (APSP) problems. Also, a comparative analysis of their performances on CPU and GPU is discussed in this paper.Write-write consistency in Bellman-Ford is overcome using synchronization mechanism available in OpenCL and by explicit synchronization by modifying the algorithm.An average speed up of 13.8x for parallel bellman ford for SSSP and an average speed up of 18.5x for bellman ford for APSP is achieved by proposed algorithm.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: