PERBANDINGAN ALGORITMA A* DENGAN ALGORITMA DIJKSTRA UNTUK PENCARIAN JARAK DAN RUTE TERPENDEK BERBASIS WEB

Abstract

Penggunaan Gas Elpiji di Kota Gorontalo mulai meningkat sejak awal tahun 2012. Hal ini dilihat dengan semakin banyaknya penyebaran pangkalan-pangkalan elpiji di Kota Gorontalo. Namun, tidak semua masyarakat mengetahui lokasi serta rute untuk menuju ke pangkalan-pangkalan tersebut. Oleh karena itu, penulis bermaksud merancang sebuah aplikasi web yang dapat menampilkan lokasi serta rute terpendek untuk sampai ke pangkalan yang akan dituju. Ada beberapa algoritma yang digunakan dalam pencarian rute terpendek, namun algoritma yang digunakan pada penelitian ini yaitu hanyalah algoritma A* dan algoritma Dijkstra. Tujuan dari penelitian ini yaitu membandingkan algoritma A* dan algoritma Dijkstra untuk melihat manakah yang lebih cepat dalam pencarian rute terpendek dari posisi awal user ke lokasi tujuan. Metode penelitian yang digunakan pada penelitian ini yaitu Metode Web Development Life Cycle (WDLC). Dimana, penulis membandingkan algoritma A* dan algoritma Dijkstra dari segi pencariannya yang sistem/aplikasinya akan dijalankan pada Web. Hasil penelitian menunjukkan perbedaan dari algoritma A* dan algoritma Dijkstra hanya ada pada perhitungan untuk mencari rute terpendek lokasi tujuan. Dimana, pada algoritma A* dapat dilakukan dengan cepat sebab tidak dilakukan pada semua node yang terhubung, hanya melihat setiap node yang bernilai kecil untuk dilewati, dan mengikuti node-node bernilai kecil tersebut hingga sampai ke lokasi tujuan. Sedangkan pada algoritma Dijkstra, pencariannya dilakukan pada semua node yang terhubung dengan lokasi awal user. Sehingga, perhitungan untuk mencari rute terpendek menjadi lambat untuk sampai ke lokasi tujuan.