Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(107.28KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Comparative Analysis of Algorithms for Single Source Shortest Path Problem
Shweta Srivastava
Pages - 288 - 294     |    Revised - 15-07-2012     |    Published - 10-08-2012
Volume - 6   Issue - 4    |    Publication Date - August 2012  Table of Contents
MORE INFORMATION
KEYWORDS
Single Source Shortest Path Problem, Dijkstra, Thorup, Heuristic Genetic Algorithm, Adjacent Node Algorithm
ABSTRACT
The single source shortest path problem is one of the most studied problem in algorithmic graph theory. Single Source Shortest Path is the problem in which we have to find shortest paths from a source vertex v to all other vertices in the graph. A number of algorithms have been proposed for this problem. Most of the algorithms for this problem have evolved around the Dijkstra’s algorithm. In this paper, we are going to do comparative analysis of some of the algorithms to solve this problem. The algorithms discussed in this paper are- Thorup’s algorithm, augmented shortest path, adjacent node algorithm, a heuristic genetic algorithm, an improved faster version of the Dijkstra’s algorithm and a graph partitioning based algorithm.
CITED BY (2)  
1 Oguike, O. E. (2013). Recursive Shortest Route Algorithm Using Abstract Data Type, Graph. African Journal of Computing & ICT, 6(2).
2 Shaikh, E. A., & Dhale, A. AGV Path Planning and Obstacle Avoidance Using Dijkstra’s Algorithm.
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Scribd
5 SlideShare
6 PdfSR
1 Y. Asano, H. Imai, “ Practical Efficiency of the Linear Time Algorithm for the Single Source Shortest Path problem”, Journal of the Operations Research, Society of Japan, Vol. 43, No. 4; 2000.
2 J. B. Orlin, K. Madduri, K. Subramani, M. Williamson, “A faster algorithm for the Single Source Shortest Path problem with few distinct positive lengths”, Journal of Discrete Algorithm; 2009.
3 B. S. Hasan, M. A. Khamees, A. S. H. Mahmoud, “A Heuristic Genetic Algorithm for the Single Source Shortest Path Problem”, IEEE International Conference on Computer Systems and Applications; 2007.
4 P. P. Mitra, R. Hasan M. Kaykobad, “On Linear time algoritm for SSSP Problem”, ICCIT, 2000.
5 Zhang Fuhao, L. Jiping, “An algorithm of shortest path based on Dijkstra for huge data”, 6thInternational Conference on Fuzzy Systems and Knowledge discovery, 2009.
6 R. H. Mohring and H. Schilling, “Partitioning Graphs to Speedup Dijkstra’s Algorithm”, ACM Journal of Experimental Algorithmics, Vol. 11, Article No. 2.8, Pages 1-29, 2006.
Mr. Shweta Srivastava
- India