Floyd-Warshall Semua Pasangan

Kadang-kadang Anda memerlukan laluan terpendek antara setiap pasangan nod, bukan hanya dari satu sumber. Itulah masalah semua pasangan.

Floyd-Warshall mengisi jadual jarak lengkap untuk semua pasangan dengan tiga gelung bersarang yang teratur dan hampir tanpa persediaan.

Gunakan matriks yang menyimpan kos terbaik yang diketahui dari i ke j dalam dist[i][j]. Mulakannya dengan sisi langsung yang diberikan.

Setiap nod boleh mencapai dirinya sendiri tanpa kos, jadi tetapkan diagonal dist[i][i] kepada sifar sebelum Anda mula melonggarkan.

Helahnya adalah membenarkan laluan melalui nod perantaraan k, kemudian menyemak sama ada laluan melalui k lebih murah daripada laluan langsung.

Gelung luar ialah k, iaitu titik tengah yang dipilih. Gelung dalam i dan j mencuba setiap pasangan berbanding titik tengah itu.

Bagi setiap pasangan, longgarkan melalui k: jika laluan dari i ke k kemudian ke j lebih pendek, kemas kini dist[i][j] kepada jumlah kos tersebut.

Apabila k selesai diproses, semua pasangan mungkin menggunakan titik perantaraan sehingga k. Meletakkan k sebagai gelung terluar memastikan jaminan itu kekal betul.

Floyd-Warshall menerima sisi negatif, tetapi bukan kitaran negatif. Kitaran negatif menyebabkan sesetengah entri pepenjuru menjadi kurang daripada sifar.

Tiga gelung merentasi n nod memberikan masa O(n^3) dan ruang O(n^2), praktikal hanya apabila n kekal sekitar beberapa ratus.

Pilih Floyd-Warshall apabila graf itu kecil dan padat dan Anda benar-benar memerlukan jarak bagi setiap pasangan, bukan hanya dari satu sumber.

Mulakan matriks, sifarkan pepenjuru, kemudian jalankan gelung k, i, j dan longgarkan melalui k. Laluan terpendek semua pasangan dalam O(n^3). 🧮