Optimalisasi Rute Menggunakan Algoritma Dijkstra dan Greedy: Sebuah Pendekatan Komparatif

Felisa Jelita; Diana Fallo; Yoseph Gayus Miru

doi:10.53863/kst.v7i01.1659

Authors

Felisa Jelita Universitas Citra Bangsa Kupang, Kupang, Indonesia
Diana Fallo Universitas Citra Bangsa Kupang, Kupang, Indonesia
Yoseph Gayus Miru Universitas Citra Bangsa Kupang, Kupang, Indonesia

DOI:

https://doi.org/10.53863/kst.v7i01.1659

Keywords:

Dijkstra algorithm, Greedy algorithm, shortest path, route optimization, algorithm comparison

Abstract

This study aims to analyze and compare the effectiveness of three algorithms that are often used in finding the shortest path, namely the Dijkstra Algorithm, the Greedy Algorithm, and the A* Algorithm. The problem of finding the shortest path is one of the basic challenges in the field of computer science, especially in applications such as navigation systems, logistics, and digital mapping. This study was conducted by conducting a literature study of more than 20 trusted scientific references published between 2015 and 2024. The results of the analysis show that the Dijkstra algorithm provides a high level of accuracy and guarantees optimal results, although it requires more time and memory. The Greedy algorithm excels in time efficiency and simplicity, but does not guarantee an optimal solution. The A* algorithm combines the strengths of Dijkstra and Greedy through a heuristic approach that promises efficiency and accuracy at the same time. This study concludes that the selection of algorithms should be adjusted to the context of their application and that the A* algorithm can be an effective compromise solution. These findings are expected to provide theoretical and practical contributions in the development of intelligent and adaptive route optimization systems.
Keywords: Dijkstra algorithm, Greedy algorithm, shortest path, route optimization, algorithm comparison

References

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.

He, B. (2022). Application of Dijkstra algorithm in finding the shortest path. Journal of Physics: Conference Series, 2181(1), 012005. IOP Publishing. https://doi.org/10.1088/1742-6596/2181/1/012005

Helgason, R. V., Kennington, J. L., & Stewart, B. D. (1993). The one-to-one shortest-path problem: An empirical analysis with the two-tree Dijkstra algorithm. Computational Optimization and Applications, 2(1), 47–75. https://doi.org/10.1007/BF01299142

Huang, Y. (2018). Research on the improvement of Dijkstra algorithm in the shortest path calculation. In Proceedings of the 2017 4th International Conference on Machinery, Materials and Computer (MACMC 2017). Atlantis Press. https://doi.org/10.2991/macmc-17.2018.141

Jiang, Z., Sahasrabudhe, V., Mohamed, A., Grebel, H., & Rojas-Cessa, R. (2019). Greedy algorithm for minimizing the cost of routing power on a digital microgrid. Energies, 12(16), 3076. MDPI. https://doi.org/10.3390/en12163076

Madkour, A., Aref, W. G., Rehman, F. U., Rahman, M. A., & Basalamah, S. (2017). A survey of shortest-path algorithms. arXiv preprint. https://arxiv.org/abs/1705.02044

Nakayama, A., & Anazawa, T. (2013). Dijkstra-based algorithms for the shortest path problem with edges of negative length. Journal of the Operations Research Society of Japan, 56(2), 137–154. https://doi.org/10.15807/jorsj.56.137

Putriani, A. D., Wamiliana, & Chasanah, S. L. (2024). Comparison of the Dijkstra’s algorithm and the Floyd-Warshall’s algorithm to determine the shortest path between hospitals in several cities in Lampung Province. Journal of Mathematical Sciences and Optimization, 1(2). https://doi.org/10.31258/jomso.v1i2.22

Rachmawati, D., & Gustin, L. (2020). Analysis of Dijkstra's algorithm and A* algorithm in shortest path problem. Journal of Physics: Conference Series, 1566(1), 012061. IOP Publishing. https://doi.org/10.1088/1742-6596/1566/1/012061

Sniedovich, M. (2019). Dijkstra's algorithm revisited: The OR/MS Connexion. University of Melbourne. https://ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html

Surorejo, S., Al Fattah, M. R., Andriani, W., & Gunawan, G. (2024). Comparison of Dijkstra and genetic algorithms for shortest path Guci. Jurnal Mandiri IT, 13(1), 56–62. https://doi.org/10.35335/mandiri.v13i1.298

Zhao, J., Chen, L., & Wang, X. (2017). Comparative study of shortest path algorithms in large-scale networks. International Journal of Computer Applications, 165(8), 22–29. https://doi.org/10.5120/ijca2017914153