Algoritma Floyd-Warshall: Menjelajahi Jalur Terpendek di Antara Semua Titik

Dalam dunia ilmu komputer dan teori graf, menemukan jalur terpendek antar dua titik dalam sebuah jaringan adalah masalah fundamental yang sering muncul. Berbagai algoritma telah dikembangkan untuk mengatasi tugas ini, dan salah satunya yang paling terkenal dan ampuh adalah Algoritma Floyd-Warshall.

Apa Itu Algoritma Floyd-Warshall?

Algoritma Floyd-Warshall, juga dikenal sebagai algoritma Floyd atau algoritma Warshall, adalah sebuah algoritma yang sangat efisien untuk menemukan jalur terpendek antar semua pasangan titik (all-pairs shortest path) dalam sebuah graf berbobot. Graf yang dimaksud di sini adalah graf berarah atau tak berarah, yang bisa memiliki bobot tepi positif maupun negatif, namun tanpa siklus negatif. Keunggulan utama algoritma ini adalah kemampuannya untuk menghitung jarak terpendek dari setiap titik ke setiap titik lainnya secara bersamaan.

Bagaimana Cara Kerjanya?

Inti dari Algoritma Floyd-Warshall terletak pada pendekatan dinamis. Algoritma ini membangun sebuah matriks jarak yang awalnya berisi bobot langsung antar pasangan titik. Kemudian, secara iteratif, algoritma ini mempertimbangkan setiap titik lain sebagai titik perantara yang potensial dalam jalur terpendek.

Misalkan kita memiliki sebuah graf dengan N titik. Algoritma ini akan menggunakan sebuah matriks dist[N][N], di mana dist[i][j] menyimpan jarak terpendek dari titik i ke titik j. Awalnya, matriks ini diinisialisasi sebagai berikut:

• Jika ada tepi langsung dari titik i ke titik j dengan bobot w, maka dist[i][j] = w.
• Jika i sama dengan j, maka dist[i][j] = 0 (jarak dari titik ke dirinya sendiri adalah nol).
• Jika tidak ada tepi langsung dari i ke j, maka dist[i][j] = infinity (atau nilai yang sangat besar untuk menandakan tidak adanya jalur langsung).

Proses iteratifnya melibatkan tiga perulangan bersarang (nested loops):

for k from 1 to N:      // Iterasi melalui setiap titik sebagai perantara potensial
  for i from 1 to N:    // Iterasi melalui setiap titik awal
    for j from 1 to N:  // Iterasi melalui setiap titik tujuan
      // Cek apakah jalur melalui titik k lebih pendek dari jalur saat ini
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
        

Dalam setiap iterasi k, algoritma memeriksa apakah jalur dari i ke j melalui titik k lebih pendek daripada jalur yang saat ini tercatat di dist[i][j]. Jika ya, maka dist[i][j] diperbarui. Setelah ketiga perulangan selesai, matriks dist akan berisi jarak terpendek dari setiap titik ke setiap titik lainnya.

Kompleksitas Waktu

Algoritma Floyd-Warshall memiliki kompleksitas waktu O(N^3), di mana N adalah jumlah titik dalam graf. Ini karena adanya tiga perulangan bersarang yang masing-masing berjalan sebanyak N kali. Meskipun terdengar besar, untuk graf dengan ukuran menengah, kompleksitas ini masih dapat diterima. Untuk graf yang sangat besar, algoritma lain seperti Bellman-Ford atau Dijkstra mungkin lebih disukai jika hanya dibutuhkan jalur terpendek dari satu titik sumber.

Kapan Menggunakan Algoritma Floyd-Warshall?

Algoritma ini sangat cocok digunakan dalam skenario berikut:

• Anda perlu mengetahui jarak terpendek antara semua pasangan titik dalam sebuah graf.
• Graf memiliki bobot tepi negatif (tetapi tidak ada siklus negatif).
• Ukuran graf tidak terlalu besar, sehingga kompleksitas O(N^3) masih bisa ditoleransi.
• Perlu menghitung keterhubungan antar komponen dalam jaringan, seperti dalam masalah routing pada jaringan komputer.

Contoh Sederhana

Bayangkan sebuah graf kecil dengan 3 titik: A, B, dan C. Kita memiliki bobot tepi sebagai berikut: A ke B (bobot 5), B ke C (bobot 3), dan A ke C (bobot 10). Jika kita menjalankan Algoritma Floyd-Warshall, setelah iterasi yang tepat, kita akan menemukan bahwa jarak terpendek dari A ke C adalah 8 (melalui B), bukan 10.

Proses ini terus berlanjut untuk semua pasangan, memastikan bahwa setiap kemungkinan jalur perantara telah dipertimbangkan untuk menemukan jalur terpendek yang sebenarnya.