CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Shortest Path Computation in Large Graphs using Bidirectional Strategy and Genetic Algorithms

by Shom C. Abraham, Girish Dutt Shukla
journal cover thumbnail

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

@article{ 10.5120/19250-0932,
author = { Shom C. Abraham, Girish Dutt Shukla },
title = { Shortest Path Computation in Large Graphs using Bidirectional Strategy and Genetic Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { January 2015 },
volume = { 109 },
number = { 13 },
month = { January },
year = { 2015 },
issn = { 0975-8887 },
pages = { 27-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume109/number13/19250-0932/ },
doi = { 10.5120/19250-0932 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:44:43.577897+05:30
%A Shom C. Abraham
%A Girish Dutt Shukla
%T Shortest Path Computation in Large Graphs using Bidirectional Strategy and Genetic Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 109
%N 13
%P 27-30
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Dijkstra, E. W. (1959), A Note on Two Problems in Connexion with Graphs, Numerishe Mathematic 1 , 269-271
  2. 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.
  3. Bellman, R. (1958), On a Routing Problem, Quart. Appl. Math. 16, 87-90.
  4. M. Ericsson, M. G. C. Resende, and P. M. Pardalos , A Genetic Algorithm for the Weight Setting Problem in OSPF Routing
  5. Goldberg, D. E. , Genetic Algorithms in Search ,Optimization, and Machine Learning, Addison-Wesley, Reading, 1989
  6. Cai, X. , Klocks, T. and Wong, C. K. (1997), Time-Varying Shortest Path Problems with Constraints, Networks, 29 , 141-149
  7. Dreyfus, S. E. (1969), An Appraisal of Some Shortest-Path Algorithms, Operations Research, 17, 395-412
  8. Floyd, R. W. (1962), Algorithm 97: shortest path. Comm. ACM 5345.
  9. 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.
  10. 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.
  11. Cherkassky, B. V. , Goldberg, A. V. and Radzik, T. (1996), Shortest path algorithms: Theory and experimental evaluation, Mathematical Programming 73, 129-174
Index Terms

Computer Science
Information Sciences

Keywords

Min Heaps Dijkstra's Algorithm Genetic Algorithms Shortest Path Computation

Powered by PhDFocusTM