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

[Full Text]

AUTHOR(S)

Kairanbay Magzhan, Hajar Mat Jani

KEYWORDS

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

ABSTRACT

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.

REFERENCES

[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.