The week's pick
Reseach Article
Shortest Path Computation in Large Graphs using Bidirectional Strategy and Genetic Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 109 - Number 13 |
| Year of Publication: 2015 |
| Authors: Shom C. Abraham, Girish Dutt Shukla |
10.5120/19250-0932
|
Shom C. Abraham, Girish Dutt Shukla . Shortest Path Computation in Large Graphs using Bidirectional Strategy and Genetic Algorithms. International Journal of Computer Applications. 109, 13 ( January 2015), 27-30. DOI=10.5120/19250-0932
Abstract
The shortest path problem in graphs is a fundamental optimization problem which has stimulated research for several decades. Numerous real-world applications are modeled as graphs and shortest path computation is a frequent operation performed on them. Many graphs happen to be very large like road networks or routing networks. Shortest path computation on them is a challenge because of the low performance due to its large nature. Already existing graph algorithms are not suitable for large graphs. In this paper, an attempt is made to solve the problem of finding an efficient point-to-point shortest path algorithm for graphs of larger sizes. First run the A * algorithm with binary heap implementation from both the directions. The nodes extracted from both directions are saved and then genetic algorithm is used to find the shortest path. The bi-directional strategy reduces the search space and the genetic algorithm optimizes the search problem to give best result. The final results illustrates that this novel approach with the optimization strategies achieves high scalability and performance.
References
- Dijkstra, E. W. (1959), A Note on Two Problems in Connexion with Graphs, Numerishe Mathematic 1 , 269-271
- Shom C. Abraham. (2013) Least Cost Path Discovery over Graphs Defined for Large Volumes of Data Satisfying Node and Link Constraints. International Journal of Computer Applications 82(12):15-18.
- Bellman, R. (1958), On a Routing Problem, Quart. Appl. Math. 16, 87-90.
- M. Ericsson, M. G. C. Resende, and P. M. Pardalos , A Genetic Algorithm for the Weight Setting Problem in OSPF Routing
- Goldberg, D. E. , Genetic Algorithms in Search ,Optimization, and Machine Learning, Addison-Wesley, Reading, 1989
- Cai, X. , Klocks, T. and Wong, C. K. (1997), Time-Varying Shortest Path Problems with Constraints, Networks, 29 , 141-149
- Dreyfus, S. E. (1969), An Appraisal of Some Shortest-Path Algorithms, Operations Research, 17, 395-412
- Floyd, R. W. (1962), Algorithm 97: shortest path. Comm. ACM 5345.
- Klein, P. N. and Subramanian, S. (1997), A Randomized Parallel Algorithm for Single-Source Shortest Paths, Journal of Algorithms, Vol. 25, No. 2, pp. 205-220.
- C. W. Ahn and R. S. Ramakrishna, A genetic algorithm for shortest path routing problem and the sizing of populations, IEEE Trans. Evol. Comput. , vol. 6, no. 6, pp. 566–579, Dec. 2002.
- Cherkassky, B. V. , Goldberg, A. V. and Radzik, T. (1996), Shortest path algorithms: Theory and experimental evaluation, Mathematical Programming 73, 129-174
Index Terms
Keywords