Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path

Muhammad Rhifky Wayahdi; Subhan Hafiz Nanda  Ginting; Dinur  Syahputra

doi:10.25008/ijadis.v2i1.1206

Authors

Muhammad Rhifky Wayahdi Department of Information System, Faculty of Technology, Battuta University, Indonesia
Subhan Hafiz Nanda Ginting Department of Information System, Faculty of Technology, Battuta University, Indonesia
Dinur Syahputra Department of Information System, Faculty of Technology, Battuta University, Indonesia

DOI:

https://doi.org/10.25008/ijadis.v2i1.1206

Keywords:

Greedy algorithm, A-Star algorithm, Dijkstra’s algorithm, Path finding, Shortest path

Abstract

The problem of finding the shortest path from a path or graph has been quite widely discussed. There are also many algorithms that are the solution to this problem. The purpose of this study is to analyze the Greedy, A-Star, and Dijkstra algorithms in the process of finding the shortest path. The author wants to compare the effectiveness of the three algorithms in the process of finding the shortest path in a path or graph. From the results of the research conducted, the author can conclude that the Greedy, A-Star, and Dijkstra algorithms can be a solution in determining the shortest path in a path or graph with different results. The Greedy algorithm is fast in finding solutions but tends not to find the optimal solution. While the A-Star algorithm tends to be better than the Greedy algorithm, but the path or graph must have complex data. Meanwhile, Dijkstra's algorithm in this case is better than the other two algorithms because it always gets optimal results.

Downloads

Download data is not yet available.

References

S. Bhosale & D. Kulkarni, "A Greedy Algorithm Approach for Mobile Social Network", International Journal of Computer Applications, volume 111, number 16, 2015. https://doi.org/10.5120/19619-1139

H.E. Zhenhuan, "Research on Improved Greedy Algorithm for Train Rescheduling", IEEE 7th International Conference on Computational Intelligence and Security, pp. 1197- 1200, 2011.

B.M. Patil & B. Amarapur, "Segmentation of Leaf Images using Greedy Algorithm", IEEE International Conference on Energy, Communication, Data Analytics and Soft Computing (ICECDS), pp. 2137-2141, 2017. https://doi.org/10.1109/ICECDS.2017.8389830

F. Duchon, A. Babinec, M. Kajan, P. Beno, M. Florek, T. Fico, & L. Jurisica, "Path Planning with Modified A Star Algorithm for a Mobile Robot", Elsevier Modelling of Mechanical and Mechatronic Systems, pp. 59-69, 2014. https://doi.org/10.1016/j.proeng.2014.12.098

R. Septiana, I. Soesanti, N.A. Setiawan, "Evaluation Function Effectiveness in Wireless Sensor Network Routing using A-Star Algorithm", IEEE 4th International Conference on Cyber and IT Service Management, pp. 1-5, 2016. https://doi.org/10.1109/CITSM.2016.7577519

H. Wang, J. Zhou, G. Zheng, & Y. Liang, "HAS: Hierarchical A-Star Algorithm for Big Map Navigation in Special Areas", IEEE International Conference on Digital Home, pp. 222-225, 2014. https://doi.org/10.1109/ICDH.2014.49

N.A.M. Sabri, A.S.H. Basari, B. Husin, & K.A.F.A. Samah, "The Utilisation of Dijkstra's Algorithm to Assist Evacuation Route in Higher and Close Building", Journal of Computer Science, pp. 330-336, 2015. https://doi.org/10.3844/jcssp.2015.330.336

M. Abderrahim, H. Hakim, H. Boujemaa, & F. Touati, "Energy-Efficient Transmission Technique Based on Dijkstra Algorithm for Decreasing Energy Consumption in WSNs", IEEE 19th International Conference on Sciences and Techniques of Automatic Control & Computer Engineering, pp. 599-604, 2019. https://doi.org/10.1109/STA.2019.8717210

J.R. Jiang, H.W. Huang, J.H. Liao, & S.Y. Chen, "Extending Dijkstra's Shortest Path Algorithm for Software Defined Networking", IEICE Asia Pasific Network Operation and Management Symposium (APNOMS), pp. 1-4, 2014. https://doi.org/10.1109/APNOMS.2014.6996609

A. Malik, A. Sharma, & V. Saroha, "Greedy Algorithm", International Journal of Scientific and Research Publications, volume 3, issue 8, ISSN 2250-3153, pp. 1-5, 2013.

R. Zhao, C. Li, X. Guo, S. Fan, Y. Wang, Y. Liu, & C. Yang, "A Parallel Iteration Algorithm for Greedy Selection Based IDW Mesh Deformation in OpenFOAM", IEEE 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE), pp. 1449-1452, 2019. https://doi.org/10.1109/EITCE47263.2019.9094931

V.P. Patel & R.K. Hardik, "Optimization of Large Join Query using Heuristic Greedy Algorithm", International Journal of Computing and Technology (IJCAT), Volume 1, Issue 1, 2014.

L. Xu, S. Lin, J. Zeng, X. Liu, Y. Fang, & Z. Xu, "Greedy Criterion in Orthogonal Greedy Learning", IEEE Transactions on Cybernetics, pp. 1-12, 2017.

H. Chen, Y. Zhou, Y.T. Tang, L. Li, & Z. Pan, "Convergence Rate of the Semi-supervised Greedy Algorithm", Elsevier Neural Networks, vol. 44, pp. 44-50, 2013. https://doi.org/10.1016/j.neunet.2013.03.001

S.B. Lin, Y.H. Rong, X.P. Sun, & Z.B. Xu, "Learning Capability of Relaxed Greedy Algorithms," IEEE Transactions on Neural Networks and Learning Systems, vol. 24, pp. 1598-1608, 2013. https://doi.org/10.1109/TNNLS.2013.2265397

K.B. Sung & D.Y. Kwak, "System Architecture for Autonomous Driving with Infrasturcture Sensors", IEEE 6th International Conference on Signal Processing and Communication Systems, pp. 1-6, 2012.

P.O.N. Saian, Suyoto, & Pranowo, "Optimized A-Star Algorithm in Hexagon-Based Environment using Parallel Bidirectional Search", IEEE 8th International Conference on Information Technology and Electrical Engineering (ICITEE), pp. 1-5, 2016. https://doi.org/10.1109/ICITEED.2016.7863246

X. Liu & D. Gong, "A Comparative Study of A-Star Algorithms for Search and Rescue in Perfect Maze", IEEE International Conference on Electric Information and Control Engineering, pp. 1-4, 2011.

S. Mahadewi, K.R. Shylaja, & M.E. Ravinandan, "Memory Based A-Star Algorithm for Path Planning of a Mobile Robot", International Journal of Science and Research (IJSR), Volume 3, Issue 6, pp. 1351-1355, 2014.

A. Candra, M.A. Budiman, & K. Hartanto, "Dijkstra's and A-Star in Finding the Shortest Path: a Tutorial", IEEE International Conference on Data Science, Artificial Intelligence, and Business Analytics (DATABIA), pp. 28-32, 2020.

https://doi.org/10.1109/DATABIA50434.2020.9190342

J. Yao, C. Lin, X. Xie, A.J. Wang, & C.C. Hung, "Path Planning for Virtual Human Motion using Improved A* Algorithm", IEEE 7th International Conference on Information Technology, pp. 1154-1158, 2010. https://doi.org/10.1109/ITNG.2010.53

S. Sedighi, D.V. Nguyen, & K.D. Kuhnert, "Guided Hybrid A-Star Path Planning Algorithm for Valet Parking Applications", IEEE 5th International Conference on Control, Automation, and Robotics, pp. 570-575, 2019. https://doi.org/10.1109/ICCAR.2019.8813752

T. Surekha & R. Santosh, "Review of Shortest Path Algorithm", International Research Journal of Engineering and Technology (IRJET), Volume 3, Issue 8, pp. 1956-1959, 2016.

Risald, A.E. Mirino, & Suyoto, "Best Routes Selection using Dijkstra and Floyd-Warshall Algorithm", IEEE International Conference on Information & Communication Technology and System (ICTS), pp. 155-158, 2017. https://doi.org/10.1109/ICTS.2017.8265662

Y. Chao, "A Developed Dijkstra Algorithm and Simulation of Urban Path Search", IEEE 5th International Conference on Computer Science & Education, pp. 1164-1167, 2010. https://doi.org/10.1109/ICCSE.2010.5593700