Algoritma Floyd–Warshall

Atlas jalan zaman dulu punya tabel di halaman belakang: jarak antara setiap pasangan kota. Floyd–Warshall adalah cara menghitung tabel seperti itu, dan termasuk algoritma terpendek yang pernah ditulis: tiga perulangan, satu perbandingan, dan semua jarak terpendek pun didapat.

Graf kecil yang sisinya punya panjang, di samping tabel jarak antara setiap pasangan simpul, dengan satu baris dan satu kolom disorot
Graf kecil yang sisinya punya panjang, di samping tabel jarak antara setiap pasangan simpul, dengan satu baris dan satu kolom disorot

Idenya

Algoritma Dijkstra dan Bellman–Ford mencari jarak terpendek dari satu awal. Floyd–Warshall mencarinya dari setiap simpul ke setiap simpul lain sekaligus, dalam tabel dengan satu baris dan satu kolom per simpul. Algoritma ini mulai dari apa yang langsung diberitahukan sisi-sisi, lalu memperbaiki seluruh tabel dengan mengizinkan makin banyak simpul sebagai titik singgah di jalan.

Langkah demi langkah

Isi tabel: 0 dari tiap simpul ke dirinya sendiri, panjang sisi di antara tetangga, dan tak hingga di tempat lain. Lalu, untuk setiap simpul k, dan untuk setiap pasangan i, j: jika jarak dari i ke k ditambah jarak dari k ke j lebih kecil daripada jarak dari i ke j, tulis angka yang lebih kecil. Itulah seluruh algoritmanya. Dalam kode, ini tiga perulangan, dengan k di paling luar.

Contoh

Ambil empat simpul dengan sisi A–B panjang 3, B–C 1, A–C 5, dan C–D 2. Tabel dimulai dengan sisi-sisi itu, dan tak hingga untuk A–D dan B–D. Putaran A tidak mengubah apa pun, karena setiap jalan lewat A lebih panjang. Putaran B menemukan A ke C lewat B: 3 + 1 = 4, lebih pendek dari 5. Putaran C menemukan A ke D lewat C: 4 + 2 = 6, dan B ke D: 1 + 2 = 3, keduanya jalan pertama yang ditemukan. Putaran D tidak mengubah apa pun. Tabel akhirnya: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Mengapa urutan perulangan penting

Titik singgah k harus menjadi perulangan terluar. Setelah putaran k, setiap entri adalah jarak terpendek yang hanya memakai k simpul pertama sebagai titik singgah, dan putaran berikutnya dibangun di atasnya: jalur terbaik lewat titik singgah baru adalah jalur terbaik ke sana ditambah jalur terbaik dari sana, keduanya sudah benar. Menaruh k di perulangan dalam merusak jaminan itu dan bisa meninggalkan jarak yang salah. Memperbarui tabel di tempat selama satu putaran aman, karena baris dan kolom k sendiri tidak berubah di putaran itu.

Sejarah dan kegunaan

Bernard Roy menjelaskan metode ini pada 1959. Pada 1962 Stephen Warshall menerbitkannya untuk penutupan transitif, yang hanya menanyakan apakah satu simpul bisa mencapai simpul lain, dan Robert Floyd menerbitkannya untuk jalur terpendek. Algoritma ini menghitung tabel jarak dan tabel routing, mencari diameter jaringan, menunjukkan simpul mana yang bisa mencapai simpul mana, dan dengan entri negatif di diagonal mengungkap siklus negatif.

Jelajahi

Buka aplikasinya dan tekan Langkah. Graf ada di satu sisi dan tabel di sisi lain. Setiap putaran menyorot baris dan kolom titik singgah saat ini; setiap langkah menulis jarak yang lebih pendek untuk satu pasangan dan memberi garis tepi pada dua entri yang dijumlahkan. Sel yang berubah di putaran ini diwarnai. Pilih awal dan tujuan untuk melihat jalur terpendek di antara keduanya saat tabel lengkap.

Pertanyaan yang sering diajukan

Berapa kompleksitas waktu Floyd–Warshall?

O(n³) untuk n simpul, berapa pun jumlah sisinya, dan memori O(n²) untuk tabel. Ini metode pilihan untuk graf kecil atau padat, tempat perulangannya yang sederhana berjalan sangat cepat.

Floyd–Warshall atau Dijkstra dari setiap simpul?

Untuk graf padat, atau jika sisi bisa negatif, Floyd–Warshall lebih sederhana dan hampir sama cepat. Untuk graf besar yang jarang dengan sisi tak negatif, menjalankan algoritma Dijkstra dari tiap simpul lebih cepat.

Apakah Floyd–Warshall termasuk pemrograman dinamis?

Ya. Algoritma ini menyelesaikan masalah untuk jalur dengan titik singgah di antara k simpul pertama memakai jawaban untuk k − 1 simpul pertama, dan hanya menyimpan satu tabel yang ditimpa sambil berjalan.

Apa itu penutupan transitif?

Tabel simpul mana yang bisa mencapai simpul mana, tanpa memedulikan jarak. Versi algoritma dari Warshall menghitungnya dengan "or" dan "and" sebagai ganti "min" dan "+".

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba Floyd–Warshall