Perbandingan Algoritma Greedy dan Algoritma Dijkstra dalam Pencarian Rute Terpendek dari Kabupaten Tuban ke Kota Surabaya
DOI:
https://doi.org/10.31980/petik.v8i2.1255Keywords:
Shortest Path, Graph, Greedy Algorithm, Dijkstra's AlgorithmAbstract
Abstrak — Menemukan jarak terpendek adalah masalah umum bagi pengguna transportasi dari awal. Hal ini dikarenakan para pengguna transportasi membutuhkan jarak yang pendek dan waktu yang singkat agar dapat mencapai perjalanan dengan cepat. Masalah transportasi sering muncul dari lokasi terpencil, terutama jika ada pengguna transportasi mencoba untuk pergi ke kota besar. Telah banyak algoritma yang digunakan untuk membantu menemukan rute terpendek dari satu kota ke kota lain diantaranya algoritma Greedy dan algoritma Dijkstra. Pada penelitian ini diimplementasi kedua algoritma tersebut untuk mencari jalur terpendek dengan cakupan wilayah dari Kabupaten Tuban (sebagai vertex T) hingga ke Kota Surabaya (sebagai vertex S). Kedua algoritma yang digunakan dibandingkan dengan menggunakan 4 (empat) parameter yaitu (1)waktu algoritma, (2) kompleksitas algoritma, (3) urutan pemrograman algoritma, dan (4) hasil jarak yang ditempuh saat menyelesaikan algoritma. Dari hasil perbandingan dapat disimpulkan bahwa algoritma Greedy lebih unggul terkait waktu eksekusi, kompleksitas, dan urutan algoritma, namun untuk hasil rute terpendek algoritma Dijkstra lebih unggul dibandingkan dengan algoritma Greedy dengan rute terpendek yang dihasilkan 105 Km, sedangkan algoritma Greedy menghasilkan rute terpendek 129 Km.
Kata Kunci — Rute Terpendek, Graf, Algoritma Greedy, Algoritma Dijkstra
Abstract — Finding distance a common problem for transport users from the start. This is because transportation users need a short distance and a short time in order to reach the trip quickly. Transportation problems often arise from remote locations, especially if there are transport users trying to go to a big city. Many algorithms have been used to help find the shortest route from one city to another, including the Greedy algorithm and Dijkstra's algorithm. In this study, the two algorithms were implemented to find the shortest path with a coverage area from Tuban Regency (as vertex T) to Surabaya City (as vertex S). The two algorithms used are compared using 4 (four) parameters, namely (1) algorithm time, (2) algorithm complexity, (3) algorithm programming sequence, and (4) distance traveled when completing the algorithm. From the comparison results, it can be concluded that the Greedy algorithm is superior in terms of execution time, complexity, and algorithm sequence, but for the shortest route, Dijkstra's algorithm is superior to the Greedy algorithm with the shortest route being 105 km, while the Greedy algorithm produces the shortest route 129 km.
Keywords— Shortest Path, Graph, Greedy Algorithm, Dijkstra's Algorithm
References
M. Syauqi, H. Ardani, M. A. Yaqin, and M. H. Suhartono, “Implementasi Graph Database untuk Menentukan Rute Perjalanan Transportasi Umum Clustering View project Fraud Detection View project,” no. February, 2019, [Online]. Available: https://www.researchgate.net/publication/330872174.
C. Cerrone, R. Cerulli, and B. Golden, “Carousel Greedy: A generalized Greedy algorithm with applications in optimization,” Comput. Oper. Res., vol. 85, no. May 2018, pp. 97–112, 2017, doi: 10.1016/j.cor.2017.03.016.
E. N. Hayati and A. Yohanes, “Pencarian Rute Terpendek Menggunakan Algoritma Greedy,” Semin. Nas. IENACO, pp. 2337–4349, 2014.
D. Grace, M. S. Tanciga, and Nurdin, “Sistem Informasi Letak Geografis Penentuan Jalur Tercepat Rumah Sakit Di Kota Palu Menggunakan Algoritma Greedy Berbasis Web,” J. Elektron. Sist. Inf. dan Komput., vol. 4, no. 2, pp. 59–76, 2018.
R. B. Oktaviandi, M. S. T. Hadi, A. G. Santoso, and N. El Maidah, “Perbandingan Algoritma Genetika dengan Algoritma Greedy Untuk Pencarian Rute Terpendek,” INFORMAL Informatics J., vol. 3, no. 1, p. 6, 2019, doi: 10.19184/isj.v3i1.9847.
A. M. Herli, I. K. Raharjana, and P. Soeparman, “Sistem Pencarian Hotel Berdasarkan Rute Perjalanan Terpendek Dengan Mempertimbangkan Daya Tarik Wisata Menggunakan Algoritma Greedy,” J. Inf. Syst. Eng. Bus. Intell., vol. 1, no. 1, p. 9, 2015, doi: 10.20473/jisebi.1.1.9-16.
Z. Jiang, V. Sahasrabudhe, A. Mohamed, H. Grebel, and R. Rojas-Cessa, “Greedy algorithm for minimizing the cost of routing power on a digital microgrid,” Energies, vol. 12, no. 16, pp. 1–19, 2019, doi: 10.3390/en12163076.
E. Darnila, M. Ula, and C. D. A. Soraya, “Optimasi Kelayakan Kondisi Pembangunan Jalan di Kota Lhokseumawe Menggunakan Algoritma Greedy,” JUKI J. Komput. dan Inform., vol. 1, pp. 9–14, 2019, [Online]. Available: https://www.ioinformatic.org/index.php/juki/article/view/3%0Ahttps://www.ioinformatic.org/index.php/JUKI/article/download/3/9.
N. A. Sudibyo, P. E. Setyawan, and Y. P. S. R. Hidayat, “Implementasi Algoritma Dijkstra dalam Pencarian Rute Terpendek Tempat Wisata di Kabupaten Klaten,” Riemann Res. Math. Math. Educ., vol. 2, no. 1, pp. 1–9, 2020, doi: 10.38114/riemann.v2i1.49.
A. R. Fadillah, P. Studi, T. Informatika, and R. Terpendek, “Sistem Pencarian Lokasi Hotel Berdasarkan Rute Terpendek Untuk Pengunjung Objek Wisata Alam Di Kota Medan Menggunakan Algoritma Dijkstra,” vol. 6, no. 1, pp. 106–111, 2019.
A. Kejriwal and P. Aqsa, “Graph Theo ry and Dijkstra ’ s Algorithm : A solution for Mumbai ’ s BEST buses,” Int. J. Eng. Sci., vol. 8, no. 10, pp. 40–47, 2019, doi: 10.9790/1813-0810014047www.theijes.com.
A. Cantona, F. Fauziah, and W. Winarsih, “Implementasi Algoritma Dijkstra Pada Pencarian Rute Terpendek ke Museum di Jakarta,” J. Teknol. dan Manaj. Inform., vol. 6, no. 1, 2020, doi: 10.26905/jtmi.v6i1.3837.
P. Tirastittam and P. Waiyawuththanapoom, “Public Transport Planning System by Dijkstra Algorithm: Case Study Bangkok Metropolitan Area,” vol. 8, no. 1, pp. 54–59, 2014, [Online]. Available: http://waset.org/publications/9997113/public-transport-planning-system-by-Dijkstra-algorithm-case-study-bangkok-metropolitan-area.
S. Orhani, “Finding the Shortest Route for Kosovo Cities Through Dijkstra ’ s Algorithm,” MIDDLE Eur. 247 Sci. Bull., no. June, 2022.
A. Subagio, B. Rahayudi, and M. A. Fauzi, “Analisis Performansi Algoritma Greedy Best First Search dan Dijkstra Pada Aplikasi Pencarian Jalur Pendonor Darah Terdekat,” Pengemb. Teknol. Inf. dan Ilmu Komput., vol. 3, no. 1, pp. 515–520, 2019.
R. Y. Bunaen Maria, Pratiwi Hanna, “Penerapan algoritma Dijkstra untuk menentukan rute terpendek dari pusat kota surabaya ke tempat bersejarah,” vol. 4, no. 1, pp. 213–223, 2022, [Online]. Available: http://www.jurnal.unidha.ac.id/index.php/jteksis/article/view/407.
S. Idwan and W. Etaiwi, “Dijkstra algorithm heuristic approach for large graph,” J. Appl. Sci., vol. 11, no. 12, pp. 2255–2259, 2011, doi: 10.3923/jas.2011.2255.2259.
J. Sauwani, V. N. Putra, and H. Agung, “Implementasi Algoritma Djikstra Untuk Menentukan Lokasi Dan Jarak Tempuh Terpendek Kampus It Di Jakarta,” J. Inform., vol. 6, no. 1, pp. 29–36, 2019, doi: 10.31311/ji.v6i1.4723.
M. A. Arsyad, D. Supriyadi, A. Veronica, L. N. Hidayah, and D. P. Pratiwi, “Penerapan Algoritma A Star Untuk Pencarian Rute Terpendek Puskesmas Rawat Inap Di Banyumas,” Conf. Electr. Eng. Telemat. Ind. Technol. Creat. Media 2019, pp. 74–82, 2019, doi: 10.29408/geodika.v4i1.2068.
R. Rizky, T. Hidayat, A. H. Nugroho, and Z. Hakim, “Implementasi Metode A*Star Pada Pencarian Rute Terdekat Menuju Tempat Kuliner di Menes Pandeglang Banten,” Geodika J. Kaji. Ilmu dan Pendidik. Geogr., vol. 4, no. 1, pp. 85–94, 2020, doi: 10.29408/geodika.v4i1.2068.
