Optimalisasi Rute Menggunakan Algoritma Dijkstra dan Greedy: Sebuah Pendekatan Komparatif
DOI:
https://doi.org/10.53863/kst.v7i01.1659Kata Kunci:
algoritma Dijkstra, algoritma Greedy, jalur terpendek, optimisasi rute, perbandingan algoritmaAbstrak
Penelitian ini bertujuan untuk menganalisis dan membandingkan efektivitas tiga algoritma yang sering digunakan dalam pencarian jalur terpendek, yaitu Algoritma Dijkstra, Algoritma Greedy, dan Algoritma A*. Masalah pencarian jalur terpendek menjadi salah satu tantangan dasar dalam bidang ilmu komputer, terutama dalam aplikasi seperti sistem navigasi, logistik, dan pemetaan digital. Penelitian ini dilaksanakan dengan melakukan studi pustaka terhadap lebih dari 20 referensi ilmiah terpercaya yang diterbitkan antara tahun 2015 hingga 2024. Hasil dari analisis menunjukkan bahwa algoritma Dijkstra memberikan tingkat akurasi yang tinggi dan jaminan hasil optimal, meskipun memerlukan waktu dan memori yang lebih besar. Algoritma Greedy unggul dalam efisiensi waktu dan kesederhanaan, tetapi tidak menjamin solusi optimal. Algoritma A* menggabungkan kekuatan Dijkstra dan Greedy melalui pendekatan heuristik yang menjanjikan efisiensi dan akurasi sekaligus. Penelitian ini menyimpulkan bahwa pemilihan algoritma sebaiknya disesuaikan dengan konteks aplikasinya dan bahwa algoritma A* dapat menjadi solusi kompromi yang efektif. Temuan ini diharapkan dapat memberikan kontribusi teoritis dan praktis dalam pengembangan sistem pengoptimalan rute yang cerdas dan adaptif.
Referensi
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
Unduhan
Diterbitkan
Cara Mengutip
Terbitan
Bagian
Lisensi
Hak Cipta (c) 2025 Felisa Jelita, Diana Fallo, Yoseph Gayus Miru
Artikel ini berlisensiCreative 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
