Home > CSC-OpenAccess Library > Manuscript Information
EXPLORE PUBLICATIONS BY COUNTRIES |
 |
 |
EUROPE |
|
MIDDLE EAST |
|
ASIA |
|
AFRICA |
| ............................. | |
|
United States of America |
|
United Kingdom |
|
Canada |
|
Australia |
|
Italy |
|
France |
|
Brazil |
|
Germany |
|
Malaysia |
|
Turkey |
|
China |
|
Taiwan |
|
Japan |
|
Saudi Arabia |
|
Jordan |
|
Egypt |
|
United Arab Emirates |
|
India |
|
Nigeria |
Comparative Analysis of Algorithms for Single Source Shortest Path Problem
Shweta Srivastava
Pages - 288 - 294 | Revised - 15-07-2012 | Published - 10-08-2012
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.
| 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 |
| 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. | |
| 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. | |
| P. P. Mitra, R. Hasan M. Kaykobad, “On Linear time algoritm for SSSP Problem”, ICCIT, 2000. | |
| 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. | |
| 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. | |
| Zhang Fuhao, L. Jiping, “An algorithm of shortest path based on Dijkstra for huge data”, 6thInternational Conference on Fuzzy Systems and Knowledge discovery, 2009. | |
Mr. Shweta Srivastava
- India
|
|
|
|
| View all special issues >> | |
|
|
