Penentuan Rute Terpendek di Wilayah Kecamatan Teluk Mutiara Menggunakan Algoritma Floyd-Warshall

Abstract

Tujuan dari penelitian ini untuk menentukan rute terpendek di wilayah Kecamatan Teluk Mutiara menggunakan algoritma Floyd-Warshall, yang secara luas diterapkan dalam teori graf untuk menyelesaikan permasalahan lintasan terpendek. Permasalahan muncul akibat banyaknya alternatif jalur yang tersedia di wilayah ini, yang sering kali menyebabkan pemilihan jalur yang tidak efisien dan berdampak pada peningkatan waktu tempuh serta konsumsi bahan bakar. Data penelitian diperoleh melalui observasi dan dokumentasi menggunakan Google Maps dan Google Earth, kemudian divalidasi melalui survei lapangan. Titik-titik persimpangan jalan dan jarak antar titik tersebut dikumpulkan dan direpresentasikan dalam bentuk graf berbobot yang terdiri dari 16 simpul dan 22 sisi. Setiap ruas jalan diberi bobot berdasarkan jarak fisiknya. Algoritma Floyd-Warshall kemudian diterapkan pada graf tersebut untuk menghitung jarak terpendek antara semua pasangan titik persimpangan. Hasilnya menunjukkan jarak optimal serta rute terpendek yang dapat dilalui dari setiap titik asal ke setiap titik tujuan. Temuan ini bermanfaat dalam pengambilan keputusan rute transportasi dan pelayanan publik di wilayah tersebut, sehingga dapat membantu mengurangi waktu tempuh dan biaya operasional