Study the optimization of Dijkstra’s Algorithm

Parmanand; Sahdev; Anuradha Dwivedi

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

Journal of Ravishankar University

Pt. Ravishankar Shukla University, Raipur, Chhattisgarh

PART-B

(SCIENCE)

ISSN: 0970-5910

Abstract View

Submit Article

Study the optimization of Dijkstra’s Algorithm

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

View HTML

View PDF

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.

Keywords:

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: