Perbandingan Algoritma Dijkstra dan Floyd-Warshall dalam Menentukan Rute Terpendek Tempat Wisata di Kulon Progo

Abstract

Tujuan penelitian ini adalah: (1) Memperoleh model matematika pencarian rute terpendek tempat wisata di Kabupaten Kulon Progo, (2) Mengetahui penyelesaian rute terpendek menggunakan algoritma Dijkstra dan algoritma Floyd-Warshall dan (3) Mengetahui perbandingan hasil penyelesain kedua algoritma. Penelitian ini merupakan penelitian terapan dengan data yang digunakan bersumber dari Dinas Pariwisata Kabupaten Kulon Progo dan Google Maps. Hasil penelitian menunjukkan bahwa: (1) Model matematika yang terbentuk berupa graf bobot tak berarah yang terdiri atas 47 node, (2) Penyelesaian menggunakan algoritma Dijkstra memerlukan iterasi sebanyak 46 kali untuk setiap pintu masuk sedangkan algoritma Floyd-Warshall sebanyak  kali iterasi. Penyelesaian algoritma Dijkstra berbentuk pohon Dijkstra hasil iterasi dari setiap pintu masuk sedangkan algoritma Floyd-Warshall berbentuk matriks dengan nilai bobot antar node terkecil dan (3) Kedua metode memiliki solusi yang eksak sehingga diperoleh jumlah rute terpendek yang sama yaitu 120 rute yang terbagi menjadi 4 pintu masuk. Perbedaan rute terdapat pada rute pintu masuk III menuju Pule Payung dengan jarak tempuh yang sama yaitu  km. Paket wisata yang terbentuk sama baik rute, jarak dan pilihan paket wisata. Penyelesaian menggunakan algoritma Dijkstra jauh lebih efisien dibandingkan dengan algoritma Floyd-Warshall karena jumlah iterasi yang dilakukan algoritma Dijkstra lebih sedikit sehingga lebih menghemat waktu pencarian rute.