Perbandingan Algoritma Djikstra dan Floyd-Warshall Untuk Membuat Data Input TSP

Zuhri, Mohamad Farkhan Fahmi
Swanjaya, Daniel
Sahertian, Julian

Prosiding SEMNAS INOTEK (Seminar Nasional Inovasi Teknologi)
Vol. 9 No. 3 (2025): Prosiding Seminar Nasional Inovasi Teknologi Tahun 2025

Optimasi rute pada pengiriman air galon sangat penting untuk efisiensi waktu dan biaya di daerah pedesaan seperti Desa Sumberejo. Penelitian ini bertujuan membandingkan kinerja waktu komputasi algoritma Dijkstra yang dijalankan secara iteratif dan Floyd-Warshall dalam menghasilkan matriks waktu tempuh terpendek dan rute antar semua pasangan pelanggan dan depot. Matriks ini ditujukan untuk input algoritma optimasi multi-stop seperti Traveling Salesman Problem (TSP). Studi kasus yang digunakan dalam penelitian ini adalah jaringan jalan riil Desa Sumberejo yang memiliki 62 node jalan dan 125 node target yaitu pelanggan dan depot dengan waktu tempuh sebagai bobot graf yang dihitung berdasarkan kondisi jalan aktual. Hasil pengujian waktu eksekusi  menunjukkan bahwa secara signifikan pendekatan Dijkstra iteratif lebih cepat dibandingkan Floyd-Warshall untuk semua skenario jumlah pelanggan yang diuji. Hasil ini menunjukan bahwa Dijkstra lebih efisien untuk pra-pemrosesan data TSP pada skala jaringan serupa.