Perbandingan Algoritma Dijkstra dan A-Star dalam Pencarian Rute Terpendek Sekolah Menengah Atas (SMA) di Kota Palangka Raya Berbasis Website
DOI:
https://doi.org/10.47111/jointecoms.v5i1.19805Keywords:
Rute Terpendek, Sekolah Menengah Atas, Algoritma Dijkstra, Algoritma A-star, Haversine FormulaAbstract
Pencarian rute terpendek adalah proses untuk menemukan jalur paling efisien antara dua titik dalam suatu graf. Masalah ini merupakan salah satu bentuk optimasi penting dalam teori graf, dengan tujuan meminimalkan total bobot lintasan, seperti jarak atau waktu tempuh. Penelitian ini bertujuan untuk merancang dan mengimplementasikan sistem pencarian rute terpendek menggunakan algoritma Dijkstra dan A-star, serta membandingkan kinerja kedua algoritma dalam konteks pencarian rute menuju Sekolah Menengah Atas (SMA) di Kota Palangka Raya. Berdasarkan data dari situs resmi dapo.kemdikbud.go.id, terdapat sekitar 28 Sekolah Menengah Atas (SMA) yang tersebar di seluruh wilayah kota ini.
Data dalam penelitian ini dikumpulkan melalui beberapa metode, termasuk observasi langsung, studi literatur, dan wawancara dengan masyarakat setempat. Pengembangan perangkat lunak mengikuti model air terjun (waterfall), yang mencakup tahapan analisis kebutuhan, desain sistem, implementasi, dan pengujian. Data koordinat sekolah diperoleh dari situs Google Maps.
Hasil dari percobaan 1 hingga percobaan 8 menunjukkan bahwa algoritma A-star secara umum menghasilkan rute yang lebih efisien, dengan rata-rata jarak 0,78 km lebih pendek dan waktu tempuh lebih cepat sekitar 4,71 menit dibandingkan algoritma Dijkstra. Namun, pada Percobaan 8, algoritma Dijkstra menunjukkan keunggulan dengan menghasilkan rute yang lebih pendek sebesar 0,17 km, waktu tempuh yang lebih cepat 0,21 menit, serta memeriksa 2 node lebih sedikit dibandingkan A-star. Penelitian ini merekomendasikan pemilihan algoritma yang sesuai dengan kondisi dan kebutuhan spesifik pengguna, serta mempertimbangkan penerapan Vincenty’s Formula untuk meningkatkan akurasi dalam pencarian nilai heuristik.
Downloads
References
Adi, N. H., Giatman, M., Simatupang, W., Afrina, A., & Watrianthos, R. (2021). Penerapan metode Dijkstrapada jalur distribusi LPG untuk penentuan jarak terpendek. Building of Informatics, Technology and Science (BITS), 3(3), 235-243.Al Hakim, R. R., Satria, M. H., Arief, Y. Z., Pangestu, A., Jaenul, A., Hertin, R. D., & Nugraha, D. (2021). Aplikasi Algoritma Dijkstradalam Penyelesaian Berbagai Masalah. Expert, 11(1), 345994.ARDYAN, S., MULYONO &SUYITNO, A. (2017) ‘Implementasi Algoritma DijkstraDalam Pencarian Rute Terpendek Tempat Wisata Di Kabupaten’, UNNES Journal of Mathematics, 6(2), pp. 108–116.Aziz, M. A. (2023, March). Implementasi Algoritma Dijkstradalam Menentukan Rute Terpendek Terhadap Destinasi Wisata Kabupaten Bojonegoro. In Prosiding Seminar Pendidikan Matematika dan Matematika (Vol. 7).
JOINTECOMS (Journal of Information Technology and Computer Science)p-ISSN: 2798-284XVolume 5, Nomor 1, Maret 2025e-ISSN: 2798-386248Cantona, A., Fauziah, F., & Winarsih, W. (2020). Implementasi algoritma Dijkstrapada pencarian rute terpendek ke museum di Jakarta. Jurnal Teknologi dan Manajemen Informatika, 6(1), 27-34.Miftahuddin, Y., Umaroh, S., & Karim, F. R. (2020). Perbandingan metode perhitungan jarak euclidean, Haversine, dan manhattan dalam penentuan posisi karyawan (Studi Kasus: Institut Teknologi Nasional Bandung). Jurnal Tekno Insentif, 14(2), 69-77.Perayoga, R., Hendradi, P., & Setiawan, A. (2023). Implementasi Algoritma DijkstraPada Pencarian Rute Terpendek Objek Wisata. KLIK: Kajian Ilmiah Informatika dan Komputer, 4(3), 1471-1482.Prasetyo, A. C., Arnandi, M. P., Hudnanto, H. S., & Setiaji, B. (2019). Perbandingan Algoritma Astar dan Dijkistra Dalam Menentukan Rute Terdekat. Sisfotenika, 9(1), 36-46.Rahayu, S., Fanni, R., & Bima, K. (2022). Perbandingan HaversineFormuladan Euclidean Distance dalam Pencarian Jarak Terdekat Rumah Penampungan Hewan (Shelter). Jurnal Ilmiah FIFO, 14(1), 25-34.Rosita, Y. D., Rosyida, E. E., & Rudiyanto, M. A. (2019). Implementation of Dijkstraalgorithm and multi-criteria decision-making for optimal route distribution. Procedia Computer Science, 161, 378-385.Setiawan, W. (2010). Pembahasan pencarian lintasan terpendek menggunakan algoritma Dijkstradan A-STAR. J. Mat. ITB.SUNARDI, S., YUDHANA, A. & KADIM, A. A.(2019) ‘Implementasi Algoritma Dijkstradan Algoritma Semut Untuk Analisis Rute Transjogja Berbasis Android’, It Journal Research and Development, 01, pp. 32–38. doi: 10.25299/itjrd.2019.vol4(1).2483.Sunardi, S., Yudhana, A., & Kadim, A. A. (2019). Implementasi Algoritma DijkstraUntuk Analisis Rute Transportasi Umum Transjogja Berbasis Android. J. Sist. Inf. Bisnis, 9(1), 32.Umar, R., Yudhana, A., & Prayudi, A. (2021). Analisis Perbandingan Algoritma Djikstra, A-star, dan Floyd Warshall dalam Pencarian Rute Terdekat pada Objek Wisata Kabupaten Dompu. Jurnal Teknologi Informasi dan Ilmu Komputer, 8(2), 227-234.Yogaswara, D., & Suhartono, S. (2017). Perbandingan Algoritma A-stardan Dijkstrapada Pencarian Jalur Evakuasi Tsunami Terpendek Menuju Shelter di Kabupaten Bantul Berbasis Aplikasi Android. Jurnal Masyarakat Informatika, 12(1), 10-18.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Journal of Information Technology and Computer Science
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
