Algoritma Floyd-Warshall adalah algoritma yang digunakan untuk mencari jalur terpendek antara setiap pasang simpul dalam graf berbobot. Algoritma ini mengambil pendekatan pemrograman dinamis untuk memperbarui dan menyimpan informasi tentang jalur terpendek yang sudah diketahui saat membangun solusi secara bertahap.
Berikut adalah langkah-langkah utama dari algoritma Floyd-Warshall:
- Inisialisasi matriks jarak: Buat matriks jarak awal dengan ukuran N x N, di mana N adalah jumlah simpul dalam graf. Setiap elemen matriks awal diisi dengan jarak langsung antara simpul-simpul yang terhubung. Jika simpul i dan j tidak terhubung, jaraknya diatur sebagai tak terhingga.
- Iterasi melalui simpul-simpul: Lakukan iterasi melalui setiap simpul dalam graf sebagai simpul perantara dalam mencari jalur terpendek antara dua simpul lainnya.
- Pembaruan matriks jarak: Untuk setiap pasangan simpul (i, j), perbarui nilai matriks jarak jika jalur melalui simpul perantara lebih pendek dari jalur sebelumnya. Ini dilakukan dengan membandingkan jarak dari simpul i ke simpul j melalui simpul perantara saat ini dengan jarak langsung antara simpul i dan j. Jika jalur melalui simpul perantara lebih pendek, perbarui nilai matriks jarak dengan jarak yang lebih pendek tersebut.
- Pengulangan iterasi: Ulangi langkah 2 dan 3 untuk setiap simpul dalam graf. Setelah semua simpul telah digunakan sebagai simpul perantara, matriks jarak akan berisi jarak terpendek antara setiap pasang simpul.
- Menemukan jalur terpendek: Setelah algoritma selesai, jalur terpendek antara setiap pasang simpul dapat ditentukan dengan menggunakan matriks jarak. Jalur terpendek antara simpul i dan j adalah jalur yang melibatkan simpul-simpul perantara yang ada dalam jalur terpendek tersebut.
Algoritma Floyd-Warshall memiliki kompleksitas waktu sebesar O(N^3), di mana N adalah jumlah simpul dalam graf. Ini membuatnya efisien untuk digunakan dalam graf berukuran sedang hingga besar. Namun, algoritma ini tidak cocok untuk graf yang sangat besar dengan jutaan simpul, karena kompleksitas waktu yang tinggi.