Perbandingan Algoritma Dijkstra dan A-Star dalam Pencarian Rute Terpendek Sekolah Menengah Atas (SMA) di Kota Palangka Raya Berbasis Website

Abstract

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.