IJBTT

Designing and Implementing Shortest and Fastest Paths; A Comparison of Bellman-Ford algorithm, A*, and Dijkstra’s algorithms
	© 2021 by IJCTT Journal
	Volume-69 Issue-5
	Year of Publication : 2021
	Authors : Al Bager A. Al Bager. R, Al Samani A. Ahmed
	DOI :  10.14445/22312803/IJCTT-V69I5P102

How to Cite?

Al Bager A. Al Bager. R, Al Samani A. Ahmed, "Designing and Implementing Shortest and Fastest Paths; A Comparison of Bellman-Ford algorithm, A*, and Dijkstra’s algorithms," International Journal of Computer Trends and Technology, vol. 69, no. 5, pp. 6-12, 2021. Crossref, https://doi.org/10.14445/22312803/IJCTT-V69I5P102

Abstract
This paper compares the performances of three path algorithms, including the Bellman-Ford algorithm, A*, and Dijkstra’s algorithm. These algorithms have found the paths in a map of Riyad,h, and the run times were compared of these algorithms. The experimental findings revealed the effectiveness of A* A search algorithm, followed by Dijkstra algorithm and Bellman-Ford algorithm. This shows that Dijkstra’s algorithm can be extended into various fields to solve problems involving the computation of the shortest distance between various locations.

Keywords
Computation, Geographic Information System, Riyadh, Road time, Shortest path.

Reference

[1] Abdulaziz, A. H., Adewale, E., and Man-Yahya, S. Improved Extended Dijkstra’s Algorithm for Software Defined Networks. International Journal of Applied Information Systems, 12 (2017) 22- 26.
[2] Ak, R., Bahrami, M. and Bozkaya, B. A time-based model and GIS framework for assessing hazardous materials transportation risk in urban areas. Journal of Transport & Health, 19 ( 2020) 100943.
[3] Ananta, M. T., Jiang, J. R., & Muslim, M. A. Multicasting with the extended Dijkstra’s shortest path algorithm for software defined networking. International Journal of Applied Engineering Research, 9(23) ( 2014) 21017-21030.
[4] Arisoylu, M. An initial analysis of packet function-aware extension to Dijkstra algorithm for wireless networks. EURASIP Journal on Wireless Communications and Networking, 2016(1)( 2016) , 65.
[5] Bauer, R., Delling, D., Schieferdecker, P., Schulters, D., and Wagner, D. Combining hierarchical and goal-directed speed-up techniques for Dijkstra`s algorithm. ACM Journal of Experimental Algorithmics, (2010) 33-42.
[6] Botea, A., Müller, M. and Schaeffer, J.,. Near optimal hierarchical path-finding. J. Game Dev., 1(1) ( 2004) 1-30.
[7] Broumi, S., Bakal, A., Talea, M., Smarandache, F., & Vladareanu, L. Applying Dijkstra algorithm for solving neutrosophic shortest path problem. In 2016 International Conference on Advanced Mechatronic Systems (ICAMechS) (2016) 412-416. IEEE.
[8] Chen, Q. and Xu, N., 2019, December. Research on the Shortest Path Analysis Method in Complex Traffic Environment Based on GIS. In 2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC) 1, 208-212. IEEE.
[9] Garcia, N. M., Lenkiewicz, P., Freire, M. M., and Monteiro, P. P. 2007. On the Performance of Shortest Path Routing Algorithms for Modeling and Simulation of Static Source Routed Networks--an Extension to the Dijkstra Algorithm. In 2007 Second international conference on systems and networks communications (ICSNC 2007) 60-60. IEEE.
[10] Gen, M., Cheng, R. and Wang, D., April. Genetic algorithms for solving shortest path problems. In Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC`97)( 1997) 401-406. IEEE.
[11] Dr. Kavita, Dr. M. Anji Reddy, Geospatial Database Creation for Town Planning Using Satellite Data under GIS Environment SSRG International Journal of Civil Engineering 4(6) (2017) 98-102.
[12] Goldberg, A.V. and Harrelson, C., January. Computing the shortest path: A search meets graph theory. In SODA 5,( 2005) 156-165).
[13] Ismail, A.T., Sheta, A. and Al-Weshah, M.. A mobile robot path planning using genetic algorithm in static environment. Journal of Computer Science, 4(4) (2008) 341-344.
[14] Jiang, J. R., Huang, H. W., Liao, J. H., and Chen, S. Y. Extending Dijkstra`s shortest path algorithm for software defined networking. In The 16th Asia-Pacific Network Operations and Management Symposium (2014) 1-4. IEEE.
[15] Kim, H., 2019. Using Geographic Information Systems (GIS) to optimize delivery system services for BCCLS libraries.
[16] Machado, A.F.D.V., Santos, U.O., Vale, H., Gonçalvez, R., Neves, T., Ochi, L.S. and Clua, E.W.G., November. Real time pathfinding with genetic algorithm. In 2011 Brazilian Symposium on Games and Digital Entertainment (2011) (215-221). IEEE.
[17] Noto, M. and Sato, H., October. A method for the shortest path search by extended Dijkstra algorithm. In Smc 2000 conference proceedings. 2000 ieee international conference on systems, man and cybernetics.`cybernetics evolving to systems, humans, organizations, and their complex interactions`cat. no. 0 3 (2000) 2316-2320. IEEE.
[18] Parvin, F., Ali, S.A., Hashmi, S.N.I. and Khatoon, A.. Accessibility and site suitability for healthcare services using GIS-based hybrid decision-making approach: a study in Murshidabad, India. Spatial Information Research,( 2020) 1-18.
[19] Pramudita, R., Heryanto, H., Handayanto, R.T., Setiyadi, D., Arifin, R.W. and Safitri, N., October. Shortest Path Calculation Algorithms for Geographic Information Systems. In 2019 Fourth International Conference on Informatics and Computing (ICIC) (2019) 1-5. IEEE.
[20] Schröder, M. and Cabral, P.. Eco-friendly 3D-Routing: A GIS based 3D-Routing-Model to estimate and reduce CO2-emissions of distribution transports. Computers, Environment and Urban Systems, 73 (2019) 40-55.
[21] Sivakumar, S., and Chandrasekar, C. Modified Dijkstra’s Shortest Path Algorithm. International Journal of Innovative Research In Computer And Communication Engineering, 2(11) (2014) 1-7.
[22] Su, P., Li, Y., Li, Y. and Shiu, S.C.K. An auto-adaptive convex map generating path-finding algorithm: Genetic Convex A. International Journal of Machine Learning and Cybernetics, 4(5)( 2013) 551-563.
[23] Zhou, T. Deep learning models for route planning in road networks. (2018).