Optimalisasi Rute Menggunakan Algoritma Dijkstra dan Greedy: Sebuah Pendekatan Komparatif
DOI:
https://doi.org/10.53863/kst.v7i01.1659Keywords:
Dijkstra algorithm, Greedy algorithm, shortest path, route optimization, algorithm comparisonAbstract
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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Felisa Jelita, Diana Fallo, Yoseph Gayus Miru

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-ShareAlike 4.0 International License that allows others to share the work with an acknowledgment of the work’s authorship and initial publication in this journal