Perbandingan Penerapan Algoritma Dijkstra dan Algoritma Kruskal untuk Menentukan Rute Terpendek dari Taman Puspa Garden Menuju SMAN 4 Sidoarjo

Elisabeth Yolanda Christin, Yosefina Finsensia Riti

Abstract


Dalam penelitian ini direncanakan mencari rute terpendek dari tujuan awal berada di Taman Puspa, menuju SMA Negeri 4 Sidoarjo sebagai tujuan akhir. Dengan membandingkan metode Dijkstra dan metode algoritma Kruskal, maka dilakukan perhitungan langkah masing-masing algoritma untuk mendapatkan hasil lintasan terpendek, waktu eksekusi algoritma program tercepat serta kompleksitas algoritma pada masing-masing algoritma. Titik-titik yang ditetapkan untuk menuju tujuan adalah 13 titik yang diwakili oleh angka-angka dan arah yang ditunjukkan dengan nama jalan yang terhubung dengan titik tersebut. Langkah-langkah yang berbeda terlibat dalam setiap metode untuk mencapai solusi yang sama. Data untuk membentuk graf ini didapatkan dari dari google maps. Hasil lintasan algoritma yang didapat adalah 6150 meter dengan waktu algoritma 0,1582 detik dari hasil implementasi algoritma Dijkstra melalui program menggunakan bahasa Python yang mencakup 68 baris kompleksitas algoritma, namun pada algoritma Kruskal yang menghasilkan lintasan algoritma 11900 meter dan waktu algoritma 0,1668 detik dihasilkan dari implementasi algoritma Kruskal oleh program menggunakan bahasa Python yang terdiri dari 72 baris kompleksitas algoritma.


Full Text:

PDF

References


Akpofure, N., & Paul, N. (2017). Anapplication of Dijkstra’s Algorithm to shortest route problem. IOSR Journal of Mathematics, 13(1), 20–32. doi:10.9790/5728-1303012032

Arifianto, S. (2012). Sistem Aplikasi Penentuan Rute Terpendek Pada Jaringan Multi Moda Transportasi Umum Menggunakan Algoritma Dijkstra. eprints.undip.ac.id.

Budihartono, E. (2016). Penerapan Algoritma Dijkstra Untuk Sistem Pendukung Keputusan Bagi Penentuan Jalur Terpendek Pengiriman Paket Barang Pada Travel. Senit, 69–78. Retrieved from https://ejournal.poltektegal.ac.id/index.php/prosiding/article/ viewFile/360/344

Bunaen Maria, Pratiwi Hanna, R. Y. (2022). Penerapan algoritma Dijkstra untuk menentukan rute terpendek dari pusat kota surabaya ke tempat bersejarah, 4(1), 213–223. Retrieved from http://www.jurnal.unidha.ac.id/index.php/jteksis/article/ view/407

Debby Kurnia Dwiyanto, Sri Nurhayati, M. . (2019). Implementasi Algoritma Kruskal untuk Distribusi Listrik (Studi Kasus PT. PLN Cabang UPJ. Jatibarang), 10(2), 71–76.

Dwijono, D. (2017). Perbandingan Hasil Perhitungan Jarak Terpendek Antara Algoritma Dijkstra dengan Pemrograman Linier. Jurnal Teknik Dan Ilmu Komputer, 6(24), 467–474. Retrieved from http://ejournal.ukrida.ac.id/ojs/index.php/JTIK/article/ view/1429/1550

Gunawan, M. I. C. (2018). Penerapan Algoritma Kruskal Dalam Mencari Lokasi Anjungan Tunai Mandiri Bank Rakyat Indonesia Cabang Bengkulu Berbasis Android, 1, 44–49.

Hariyati, Nunuk, & Pangaribuan, E. N. (2019). Implementasi Kebijakan Sistem Zonasi Penerimaan Peserta Didik Baru Jenjang Smp Di Kabupaten Gresik. Inspirasi Manajemen Pendidikan, 7(1), 1–12.

Hayu, W., Yuliani, & Sam, M. (2017). Pembentukan Pohon Merentang Minimum Dengan Algoritma Kruskal. Jurnal Scientific Pinisi, Vol 3(1994), 108–115.

Kai, N., Yao-ting, Z., & Yue-peng, M. (2014). Shortest Path Analysis Based on Dijkstra’s Algorithm in Emergency Response System. Telkomnika Indonesian Journal of Electrical Engineering, 12(5), 3476–3482. doi:10.11591/telkomnika.v12i5.3236

Laurentinus, V. J. (2018). Aplikasi sistem informasi rumah kost kota pangkalpinang berbasis android menggunakan algoritma Dijkstra, 8–9.

Li, H., Xia, Q., & Wang, Y. (2017). Research and Improvement of Kruskal Algorithm. Journal of Computer and Communications, 05(12), 63–69. doi:10.4236/jcc.2017.512007

Magnolia, C., Subarkah, P., Firmanda, R. A., & Utama, D. P. (2021). Analisa Rute Transjateng Rute Purwokerto – Purbalingga Dengan Algoritma Dijkstra. DoubleClick: Journal of Computer and Information Technology, 5(1), 1. doi:10.25273/doubleclick.v5i1.9593

Meilidyaningtyas Cantika Ryadiani, Nurul Ardianingsih, R. M. (2012). Implementasi Algoritma Kruskal untuk Optimasi Pengangkutan Sampah. In Pusat Perbukuan Kementrian Pendidikan Nasional (Vol. 7, pp. 1–116).

Melnikov, B. F., & Terentyeva, Y. Y. (2021). Building communication networks: On the application of the Kruskal’s algorithm in the problems of large dimensions. IOP Conference Series: Materials Science and Engineering, 1047(1), 0–7. doi:10.1088/1757-899X/1047/1/012089

Messe Febi, B. S. (2015). Perbandingan Algoritma Dijkstra dan Best First Search untuk Penentuan Jalur Apotek Terdekat. Riskesdas 2018, 3, 103–111. Retrieved from https://publikasi.uyelindo.ac.id/index.php/semmau/article/view/64/42

Prasetyo, B. I. A., & Maslan, A. (2020). Analisis Perbandingan Pada Algoritma Bellman Ford Dan Dijkstra Pada Google Map. Khazanah Ilmu Berazam, 3(2), 337–349. Retrieved from file:///C:/Users/Lenovo/Downloads/document.pdf

Raharjo, M. I., & Susilawati, I. (2019). Aplikasi Pencarian Rute Terdekat Wisata Kota Yogyakarta Menggunakan Algoritma Dijkstra. Seminar Multimedia & Artificial Intelligence, 2(November), 158–163.

Rozikin, S., Amir, H., & Rohiat, S. (2018). Hubungan Minat Belajar Siswa Dengan Prestasi Belajar Siswa Pada Mata Pelajaran Kimia Di Sma Negeri 1 Tebat Karai Dan Sma Negeri 1 Kabupaten Kepahiang. Alotrop, 2(1), 78–81. doi:10.33369/atp.v2i1.4740

Sudibyo, N. A., Setyawan, P. E., & Hidayat, Y. P. S. R. (2020). Implementasi Algoritma Dijkstra dalam Pencarian Rute Terpendek Tempat Wisata di Kabupaten Klaten. Riemann: Research of Mathematics and Mathematics Education, 2(1), 1–9. doi:10.38114/riemann.v2i1.49

sulaiman, dady. (2021). Penerapan Algoritma Kruskal Pada Jaringan Kabel di Tanjung Selor. Wahana Matematika Dan Sains: Jurnal Matematika, Sains, Dan Pembelajarannya, 15(2), 1–15. Retrieved from https://ejournal.undiksha.ac.id/ index.php/JPM/article/view/28512

Wattimena, A. Z., & Lawalatta, S. (2013). Aplikasi Algoritma Kruskal Dalam Pengotimalan Panjang Pipa. Barekeng: Jurnal Ilmu Matematika Dan Terapan, 7(2), 13–18. doi:10.30598/barekengvol7iss2pp13-18

Yogaswara, D. (2017). Perbandingan Algoritma A-Star dan Dijkstra pada Pencarian Jalur Evakuasi Tsunami Terpendek Menuju Shelter di Kabupaten Bantul Berbasis Aplikasi Android. Jurnal Masyarakat Informatika, 12(10), 2777–0648. Retrieved from https://ejournal.undip.ac.id/index.php/jmasif/article/view/41018

Zhang, B., Fang, J., & Xiong, Z. (2018). Work-flow Push System Based on Kruskal Algorithm Location. Journal of Physics: Conference Series, 1087(2). doi:10.1088/1742-6596/1087/2/022023




DOI: https://doi.org/10.37012/jtik.v9i1.1345

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 Elisabeth Yolanda Christin

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Address:
Universitas Mohammad Husni Thamrin
Jl. Raya Pd. Gede No.23-25, RT.2/RW.1, Dukuh, Kec. Kramat jati, Kota Jakarta Timur, Daerah Khusus Ibukota Jakarta 13550

Creative Commons License
Jurnal Teknologi Informatika & Komputer Mohammad Husni Thamrin is licensed under a Creative Commons Attribution 4.0 International License.

View My Stats