Dalam dunia ilmu komputer dan matematika, pencarian jalur terpendek adalah salah satu masalah fundamental yang memiliki banyak aplikasi praktis. Mulai dari navigasi GPS, routing jaringan, hingga penjadwalan tugas, kita seringkali dihadapkan pada kebutuhan untuk menemukan cara paling efisien untuk berpindah dari satu titik ke titik lain. Ada berbagai algoritma yang dirancang untuk tujuan ini, dan salah satu yang paling kuat dan serbaguna adalah Algoritma Floyd-Warshall.
Berbeda dengan algoritma lain seperti Dijkstra yang biasanya berfokus pada pencarian jarak terpendek dari satu titik sumber ke semua titik lain, Floyd-Warshall memiliki cakupan yang lebih luas. Algoritma ini secara efektif mampu menghitung jarak terpendek antara semua pasangan titik (node) dalam sebuah graf berbobot. Graf ini bisa berarah maupun tidak berarah, dan yang terpenting, algoritma ini juga mampu menangani graf yang memiliki bobot tepi negatif, asalkan tidak ada siklus negatif.
Inti dari Algoritma Floyd-Warshall adalah penggunaan pendekatan pemrograman dinamis. Algoritma ini bekerja dengan membangun sebuah matriks jarak yang pada akhirnya akan menyimpan jarak terpendek antara setiap pasangan simpul. Mari kita sebut matriks ini sebagai dist[i][j], yang merepresentasikan jarak terpendek dari simpul i ke simpul j.
Prosesnya melibatkan iterasi melalui setiap simpul yang mungkin dijadikan sebagai "simpul perantara" (intermediate vertex). Untuk setiap simpul perantara k, algoritma memeriksa apakah jalur dari simpul i ke simpul j yang melalui simpul k lebih pendek daripada jalur yang sudah diketahui sebelumnya.
Secara matematis, pembaruan jarak dilakukan menggunakan relasi rekursif berikut:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Proses ini diulang untuk semua kemungkinan pasangan (i, j) dan untuk setiap simpul k sebagai perantara. Algoritma ini memiliki tiga loop bersarang, yang semuanya berjalan dari 0 hingga V-1, di mana V adalah jumlah total simpul dalam graf.
dist[V][V].
dist[i][j] diinisialisasi dengan bobot tepi dari i ke j jika ada.dist[i][i] diinisialisasi dengan 0 (jarak dari simpul ke dirinya sendiri adalah nol).i dan j, dist[i][j] diinisialisasi dengan nilai tak terhingga (misalnya, menggunakan konstanta yang sangat besar seperti INT_MAX dalam C++ atau float('inf') dalam Python).k dari 0 hingga V-1:i dari 0 hingga V-1:j dari 0 hingga V-1:dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Pastikan untuk menangani nilai tak terhingga agar tidak terjadi overflow.
// V adalah jumlah simpul
// graph[i][j] adalah bobot tepi dari i ke j
// Jika tidak ada tepi, graph[i][j] adalah infinity
function FloydWarshall(graph[V][V]):
dist[V][V]
// Inisialisasi matriks jarak
for i from 0 to V-1:
for j from 0 to V-1:
dist[i][j] = graph[i][j]
// Terapkan algoritma
for k from 0 to V-1: // Simpul perantara
for i from 0 to V-1: // Simpul sumber
for j from 0 to V-1: // Simpul tujuan
// Jika simpul k ada di antara i dan j, dan jaraknya lebih pendek
if dist[i][k] != infinity and dist[k][j] != infinity and dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Keunggulan:
dist[i][i] < 0 untuk suatu simpul i, maka graf tersebut mengandung siklus negatif.Keterbatasan:
V adalah jumlah simpul. Ini membuatnya kurang efisien untuk graf yang sangat besar dibandingkan dengan algoritma yang hanya mencari dari satu sumber.Algoritma Floyd-Warshall sangat berguna dalam berbagai skenario, antara lain:
Secara keseluruhan, Algoritma Floyd-Warshall adalah alat yang sangat ampuh untuk analisis jarak terpendek dalam sebuah graf, terutama ketika kebutuhan kita adalah mengetahui semua jalur terpendek antar semua pasangan simpul.