International Journal of Scientific & Technology Research

IJSTR@Facebook IJSTR@Twitter IJSTR@Linkedin
Home About Us Scope Editorial Board Blog/Latest News Contact Us

IJSTR >> Volume 2- Issue 6, June 2013 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

A Review And Evaluations Of Shortest Path Algorithms

[Full Text]



Kairanbay Magzhan, Hajar Mat Jani



Index Terms: Bellman-Ford Algorithm, Computer Networks, Dijkstra’s Algorithm, Floyd-Warshall Algorithm, Genetic Algorithm (GA), Shortest Path Problem.



Abstract: Nowadays, in computer networks, the routing is based on the shortest path problem. This will help in minimizing the overall costs of setting up computer networks. New technologies such as map-related systems are also applying the shortest path problem. This paper’s main objective is to evaluate the Dijkstra’s Algorithm, Floyd-Warshall Algorithm, Bellman-Ford Algorithm, and Genetic Algorithm (GA) in solving the shortest path problem. A short review is performed on the various types of shortest path algorithms. Further explanations and implementations of the algorithms are illustrated in graphical forms to show how each of the algorithms works. A framework of the GA for finding optimal solutions to the shortest path problem is presented. The results of evaluating the Dijkstra’s, Floyd-Warshall and Bellman-Ford algorithms along with their time complexity conclude the paper.



[1] C. Xi, F. Qi, and L. Wei, “A New Shortest Path Algorithm based on Heuristic Strategy,” Proc. of the 6th World Congress on Intelligent Control and Automation, Vol. 1, pp. 2531–2536, 2006.

[2] B.S. Hasan, M.A. Khamees, and A.S.H. Mahmoud, “A Heuristic Genetic Algorithm for the Single Source Shortest Path Problem, ” Proc. of International Conference on Computer Systems and Applications, pp. 187-194, 2007.

[3] T. Li, L. Qi, and D. Ruan, “An Efficient Algorithm for the Single-Source Shortest Path Problem in Graph Theory”, Proc. of 3rd International Conference on Intelligent System and Knowledge Engineering, Vol. 1, pp. 152-157, 2008.

[4] M. Jordan, “Notes 7 for CS170”, UC Berkeley, 2005.

[5] J. Chamero, “Dijkstra’s Algorithm” Discrete Structures & Algorithms, 2006.

[6] S. Skiena, A. Revilla, “Programming Challenges, The Programming Contest Training Manual” pp. 248 – 250.

[7] S. Hougardy, The Floyd-Warshall, “Algorithm on Graphs with Negative Cycles”, University of Bonn, 2010.

[8] M. Negnevitsky, Artificial Intelligence: A Guide to Intelligent Systems, Third Edition, Addison-Wesley, 2011.

[9] I. Rakip, U. Atila, “A Genetic Algorithm Approach for Finding the Shortest Driving Time on Mobile Devices”, Scientific Research and Essays, Dept. of Computer Engineering, 2011.

[10] Dijkstra’s Algorithm, Available at http://informatics.mccme.ru/moodle/mod/statements/view.php?id=193#1. 2012.

[11] Floyd-Warshall Algorithm, Available at http://informatics.mccme.ru/moodle/mod/statements/view.php?id=218#1. 2012.

[12] Bellman-Ford Algorithm, Available at http://informatics.mccme.ru/moodle/mod/statements/view.php?id=260#1. 2012.