Call for Paper - April 2023 Edition
IJCA solicits original research papers for the April 2023 Edition. Last date of manuscript submission is March 20, 2023. Read More

A Fine Tuned Hybrid Implementation for Solving Shortest Path Problems using Bellman Ford

International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 99 - Number 2
Year of Publication: 2014
Gaurav Hajela
Manish Pandey

Gaurav Hajela and Manish Pandey. Article: A Fine Tuned Hybrid Implementation for Solving Shortest Path Problems using Bellman Ford. International Journal of Computer Applications 99(2):29-33, August 2014. Full text available. BibTeX

	author = {Gaurav Hajela and Manish Pandey},
	title = {Article: A Fine Tuned Hybrid Implementation for Solving Shortest Path Problems using Bellman Ford},
	journal = {International Journal of Computer Applications},
	year = {2014},
	volume = {99},
	number = {2},
	pages = {29-33},
	month = {August},
	note = {Full text available}


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.


  • Michael J. Bannister and David Eppstein , "Randomized Speedup of the Bellman Ford Algorithm" in arXiv:1111. 5414v1 [cs. DS] 23 Nov 2011.
  • Andrew V. Goldberg, Tomasz Radzik , A Heuristic improvement of the Bellman Ford algorithm. Appl. Math. Lett. Vol. 6, No. 3, pp. 3-6, 1993.
  • A. S. Nepomniaschaya, An Associative Version of the Bellman-Ford Algorithm for Finding the Shortest Paths in Directed Graphs, V. Malyshkin (Ed. ): PaCT 2001, LNCS 2127, pp. 285–292, 2001.
  • J. Y. Yen. , An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of Applied Mathematics 27:526-530, 1970.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Problem 24-1: Yen's improvement to Bellman Ford. Introduction to Algorithms, 2nd edition, pp. 614-615. MIT Press, 2001.
  • R. Bellman. On a routing problem. Quarterly of Applied Mathematics 16:87-90,1958.
  • Yefim Dinitz , Rotem Itzhak , Hybrid Bellman-Ford-Dijkstra Algorithm.
  • Ayd?n Buluc , John R. Gilbert and Ceren Budak , "Solving Path Problems on the GPU" , Journal Parallel Computing Volume 36 Issue 5-6, June,2010 Pages 241-253.
  • Andrew Davidson , Sean Baxter, Michael Garland , John D. Owens , "Work-Efficient Parallel GPU Methods for Single-Source Shortest Path " in International Parallel and Distributed Processing Symposium, 2014
  • Owens J. D. , Davis, Houston, M. , Luebke, D. , Green, S. , "GPU Computing", in: Proceedings of the IEEE, Volume: 96 , Issue: 5 , 2008.
  • A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, "OpenCL Programming Guide", Addison-Wesley pub. , 2011.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition. The MIT Press, Sep. 2001.
  • Kumar, S. ; Misra, A. ; Tomar, R. S. ,"A modified parallel approach to Single Source Shortest Path Problem for massively dense graphs using CUDA" in Computer and Communication Technology (ICCCT), 2011 2nd International Conference on , vol. , no. , pp. 635,639, 15-17 Sept. 2011.
  • Atul Khanna, John Zinky , "The Revised ARPANET Routing Metric", in 1969 ACM.
  • Gaurav Hajela, Manish Pandey, "Parallel implementations for solving shortest path problem using Bellman-Ford" in IJCA June 2014 edition