Floyd-Warshall untuk Semua Pasangan

Terkadang Anda memerlukan jalur terpendek antara setiap pasangan simpul, bukan hanya dari satu sumber. Itulah masalah semua pasangan.

Floyd-Warshall mengisi tabel jarak lengkap untuk semua pasangan dengan tiga perulangan bersarang yang rapi dan hampir tanpa persiapan.

Gunakan sebuah matriks dengan dist[i][j] sebagai biaya terbaik yang diketahui dari i ke j. Mulailah dengan sisi langsung yang diberikan kepada Anda.

Setiap simpul dapat mencapai dirinya sendiri tanpa biaya, jadi atur diagonal dist[i][i] menjadi nol sebelum mulai melakukan relaksasi.

Triknya adalah mengizinkan jalur melewati simpul perantara k, lalu memeriksa apakah rute melalui k lebih murah daripada rute langsung.

Perulangan terluar adalah k, yaitu titik tengah yang dipilih. Perulangan dalam i dan j mencoba setiap pasangan terhadap titik tengah tersebut.

Untuk setiap pasangan, relaksasikan melalui k: jika jalur dari i ke k lalu ke j lebih pendek, perbarui dist[i][j] dengan biaya gabungan tersebut.

Ketika pemrosesan k selesai, semua pasangan dapat menggunakan simpul perantara hingga k. Menempatkan k di perulangan terluar menjaga agar jaminan tersebut tetap benar.

Floyd-Warshall menerima sisi negatif, tetapi tidak menerima siklus negatif. Siklus negatif membuat beberapa entri diagonal bernilai kurang dari nol.

Tiga perulangan atas n simpul menghasilkan waktu O(n^3) dan memori O(n^2), sehingga praktis hanya ketika n berjumlah beberapa ratus.

Pilih Floyd-Warshall ketika graf berukuran kecil dan padat dan Anda benar-benar memerlukan jarak untuk setiap pasangan, bukan hanya dari satu sumber.

Inisialisasikan matriks, nolkan diagonal, lalu lakukan perulangan k, i, j dan relaksasikan melalui k. Jalur terpendek semua pasangan dalam O(n^3). 🧮