A Fine Tuned Hybrid Implementation for Solving Shortest Path Problems using Bellman Ford
Gaurav Hajela, Manish Pandey · International Journal of Computer Applications · 2014
In this paper a hybrid implementation for Bellman-Ford to solve shortest path problems is proposed using OpenCL.Here first parallel implementation for Bellman-Ford for single source shortest path (SSSP) problem and all pair shortest path (APSP) are analyzed on CPU and GPU and based on this analysis work is divided among CPU and GPU and hybrid implementation is done.As proper resource utilization is done here we have termed it a fine tuned implementation.We have got considerable speedup of 2.88x over parallel implementation on GPU for SSSP and 3.3x over parallel implementation of Bellman-Ford for APSP on GPU.