A Modification of Shortest Path Algorithm According to Adjustable Weights Based on Dijkstra Algorithm

Jabbar, Luay S.; Abass, Eyad I.; Hasan, Sundus D.

doi:10.30684/etj.2022.136107.1296

	A Modification of Shortest Path Algorithm According to Adjustable Weights Based on Dijkstra Algorithm
Engineering and Technology Journal
Article 8, Volume 41, Issue 2, February 2023, Pages 359-374 PDF (1.83 M)
Document Type: Research Paper
DOI: 10.30684/etj.2022.136107.1296
Authors
Luay S. Jabbar^* ¹; Eyad I. Abass²; Sundus D. Hasan³
¹University of Technology
²Electrical Department - Lecture - University of technology
³UNIVERSITY OF TECHNOLOGY
Abstract
It is possible to represent the road map on the paper and study it using Dijkstra`s algorithm to find the shortest path on the real earth. Dijkstra`s Algorithms are used for calculating the shortest path from source to sink to enable query operations that follow. Dynamic shortest-route techniques are needed to accommodate the modifications within the underlying community topology. Every solution includes figuring out the nodes whose shortest routes could be impacted through the updates and producing a list of affected vertices and their updated shortest pathways. In this work, the advent of the retroactive priority queue information structure makes the Dijkstra algorithm dynamic. In this research, the stepping is changed forward in the shortest direction for 2 networks and two directions. That changed by locating the shortest static path, then circulating to the first node after the beginning node. At this node, the weights inside the segments directed from this node will exchange and cancel the vintage shortest direction and locate the new direction. Then flow to the next node in the new find shortest path, and repeat the operation until the end. The idea is that the best path can be constantly changed based on the latest data. These continuous changes are addressed in this paper, where the proposed system can find the best methods and update them automatically according to the variables.
Highlights
Dijkstra algorithm was used in this study. The shortest path was found using the Dijkstra algorithm for static weights for each of the single-direction and two-direction maps The dynamic shortest path was found using the Dijkstra algorithm according to changing the following weights for each of single direction and two-direction maps
Keywords
Shortest path; Adaptive path weighted; Modification of Dijkstra algorithm; practical shortest path; optimal path

References
[1] G.GALLO, Reoptimization Procedures in Shortest Path Problems, J. Nature springer.3 (1980) 3–13. doi.org/10.1007/BF02092136 [2] B. Xiao, J. Cao, Z. Shao, E.H.-M. Sha, An Efficient Algorithm for Dynamic Shortest Path Tree Update in Network Routing, J. J. Commun. Networks, Sci. 9 (2007) 499–510. doi: 10.1109/JCN.2007.6182886 [3] Y. Sharma, S.C. Saini, M. Bhandhari, Comparison of Dijkstra’s Shortest Path Algorithm with Genetic Algorithm for Static and Dynamic Routing Network, International Journal of Electronics and Computer Science Engineering, 1 (2012) 416-425. [4] U.A. Okengwu, E.O. Nwachukwu, Modified Dijkstra Algorithm for Determining Multiple Source Shortest Path of Hospital Location in Rivers State (Nigeria), J. Global Journal of Engineering Science and Research Management ,1 (2014) 46-50. [5] H. Abu-Ryash, Dr.A. Tamimi , Comparison Studies for Different Shortest Path Algorithms, J. International Journal of Computers Technology, Sci. 14 (2015) 5979-5986. [6] K. A. Fariza. Abu Samah, B. Hussin, A.H. Basari, Modification of Dijkstra’s Algorithm for Safest and Shortest Path during Emergency Evacuation, Faculty of Information Technology and Communication Universiti ,Teknikal Malaysia Melaka (UTeM) 76100 Durian Tunggal, Applied Mathematical Sciences, 9 (2015) 1531 – 1541.doi.org/10.12988/ams.2015.49681 [7] E.N. Tamatjita, A.W. Mahastama, Shortest Path with Dynamic Weight Implementation Using Dijkstra`s Algorithm, J. Binus . Sci. 7 (2016) 161-171. doi.org/10.21512/comtech.v7i3.2534 [8] M. Malathi, Optimal Path Planning for Mobile Robots Using Particle Swarm Optimization and Dijkstra Algorithm with Performance Comparison, Middle-East Journal of Scientific Research. 24 (2016) 312-320. doi.10.5829/idosi.mejsr.2016.24.S1.65 [9] H. Zhang, M. Li, Rapid path planning algorithm for mobile robot in dynamic environment, journals.sagepub.com/home/ade, Adv. Mech. Eng.9 (2017) 1-12. doi.10.1177/1687814017747400 [10] S., D. Garg, Dynamizing Dijkstra, A Solution to Dynamic Shortest Path Problem through Retroactive Priority Queue, Journal of King Saud University-Computer and Information Sciences ,33(2018)1-21. doi.org/10.1016/j.jksuci.2018.03.003 [11] J.B. Singh, R.C. Tripathi, Investigation of Bellman–Ford Algorithm, Dijkstra's Algorithm for suitability of SPP, International Journal of Engineering Development and Research, 6 (2018) 755-758. [12] A. Alyasin, E.I. Abbas, S.D. Hasan, An Efficient Optimal Path Finding for Mobile Robot Based on Dijkstra Method, In: 4th Scientific International Conference – Najaf – IRAQ. 2019,11-14. doi. 10.1109/SICN47020.2019.9019345 S.W.G. AbuSalim, R. Ibrahim, M. Saringat, S. Jamel, J.A. Wahab, Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization, In: International Conference on Technology, Engineering and Sciences (ICTES), IOP Conf. Series: Materials Science and Engineering. 917,2020,012077. doi:10.1088/1757-899X/917/1/012077 [13] Rawaa J. Abdul Kadhim, Optimum Path Finding for Mobile Robot Based on Artificial Intelligent Systems. M.Sc. Thesis, University of Technology , Baghdad, 2020.
Statistics Article View: 686 PDF Download: 570