Abstract View

Author(s): Parmanand, Sahdev, Anuradha Dwivedi

Email(s): Email ID Not Available

Address: 1Department of Mathematics, Govt. M.V.P.G. College Mahasamund (Affiliated by Pt. Ravishankar Shukla University, Raipur, Chhattisgarh-492010) 2Research Scholar, Department of Chemistry, Government Engineering College, Raipur, Chhattisgarh, India 3Research Scholar, Department of Mathematics, Government Engineering College, Raipur, Chhattisgarh, India *Corresponding Author: paramtyping@gmail.com

Published In:   Volume - 37,      Issue - 2,     Year - 2024

DOI: 10.52228/JRUB.2024-37-2-18  

ABSTRACT:
This paper presents an optimized approach to the shortest path problem, a fundamental concern in graph theory, by improving node selection and data storage. The traditional Dijkstra's algorithm is enhanced by introducing a novel node selection strategy that prioritizes nodes with the most significant impact on the shortest path, minimizing redundant calculations and accelerating convergence. Additionally, a compact data storage structure is introduced, reducing memory requirements while maintaining accuracy. This optimized approach offers reduced storage needs, enhanced efficiency, and improved scalability, making it an ideal solution for real-world applications in network optimization, traffic routing, and logistics, enabling faster and more scalable solutions for large-scale graphs and complex networks.

Cite this article:
Parmanand, Sahdev and Dwivedi (2024). Study the optimization of Dijkstra’s Algorithm. Journal of Ravishankar University (Part-B: Science), 37(2), pp. 255-267. DOI:DOI: https://doi.org/10.52228/JRUB.2024-37-2-18


References

Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

Bang-Jensen, J., & Gutin, G. (2000). Digraphs: Theory, Algorithms and Applications. Springer.

Berge, C. (1962). The Theory of Graphs and Its Applications. Wiley.

Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory with Applications. Macmillan.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Coding C Android Application Version 3.3.0 ( 2021, August), source: https://play.google.com/store/apps/details?id=com.kvassyu.coding2.c

Diestel, R. (2017). Graph Theory. Springer.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271

Even, S. (1979). Graph Algorithms. Computer Science Press.

Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596-615.

Gbadamosi, O. A., & Aremu, D. R. (2020, March). Design of a Modified Dijkstra’s Algorithm for finding alternate routes for shortest-path problems with huge costs. In 2020 International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS) (pp. 1-6). IEEE

Goldberg, A.V., Harrelson, C. "Computing the Shortest Path: A* Search Meets Graph Theory," Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.

Gondran, M., & Minoux, M. (1984). Graphs and Algorithms. Wiley.

Gross, J. L., & Yellen, J. (2004). Graph Theory and Its Applications. CRC Press.

Harary, F. (1969). Graph Theory. Addison-Wesley.

Jungnickel, D. (1999). Graphs, Networks and Algorithms. Springer.

Knuth, D. E. (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.

Korte, B., & Vygen, J. (2012). Combinatorial Optimization: Theory and Algorithms. Springer.

Meyer, U., Sanders, P. "Δ-stepping: a parallelizable shortest path algorithm," Journal of Algorithms, 2003.

Ore, O. (1962). Theory of Graphs. American Mathematical Society.

Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice Hall.

Pixellab Android Application, version 2.1.3 (2015, April), source: https://play.google.com/store/apps/details?id=com.imaginstudio.imagetools.pixellab)

Qing, G., Zheng, Z., & Yue, X. (2017, May). Path-planning of automated guided vehicle based on improved Dijkstra algorithm. In 2017 29th Chinese control and decision conference (CCDC) (pp. 7138-7143). IEEE

Sanders, P., Schultes, D. "Engineering fast route planning algorithms," Proceedings of the European Symposium on Algorithms, 2005.

Sedgewick, R. (1983). Algorithms. Addison-Wesley.

Tarjan, R. E. (1983). Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics.

Tiong, Alec Zehst M., Celeste June Gutierrez Panganiban, Mark Christopher Rodriguez Blanco, Dan Michael Cortez , May (2022). Enhancement of Dijkstra Algorithm for Finding Optimal Path, https://www.researchgate.net/publication/361145136_Enhancement_of_Dijkstra_Algorithm_for_Finding_Optimal_Path.

Wayahdi, M. R., Ginting, S. H. N., & Syahputra, D. (2021). Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path. International Journal of Advances in Data and Information Systems, 2(1), 45-52.

West, D. B. (2001). Introduction to Graph Theory. Prentice Hall.

Wilson, R. J. (1996). Introduction to Graph Theory. Longman.

Related Images:



Recent Images



A Review on role of Congestion Control Techniques in Internet of Things
Recent Advancement in Capsule: Emerging Novel Technologies and Alternative Shell Materials for Wide Range of Therapeutic Needs
Effect of L-Dopa on cypermethrin induced reproductive conditions in female Japanese quail, Coturnix coturnix japonica
Preparation, Characterization, and Applications of Albumin Serum-Based Nanoparticles
Study of developmental stages and morphometrics of Parthenium beetle in Bastar plateau agro-climatic zone of Chhattisgarh
PANI Incorporated Fe-MOF: As an Electrode Material for Supercapacitor
Surface Modified Magnetic Nanoparticles as an Efficient Material for Wastewater Remediation: A Review
A Review on Groundwater Pollution in India and their Health Problems
Incidence of Chronic fever in Raigarh Development Block of Raigarh District, Chhattisgarh, India
Study the optimization of Dijkstra’s Algorithm

Tags


Recomonded Articles:

Author(s): Parmanand; Sahdev; Anuradha Dwivedi

DOI: 10.52228/JRUB.2024-37-2-18         Access: Open Access Read More