Floyd-Warshall untuk Semua Pasangan
Jalur terpendek antara setiap pasangan
Floyd-Warshall untuk Semua Pasangan adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Setiap Pasangan Sekaligus
Terkadang Anda memerlukan jalur terpendek antara setiap pasangan simpul, bukan hanya dari satu sumber. Itulah masalah semua pasangan.
Temui Floyd-Warshall
Floyd-Warshall mengisi tabel jarak lengkap untuk semua pasangan dengan tiga perulangan bersarang yang rapi dan hampir tanpa persiapan.
Matriks Jarak
Gunakan sebuah matriks dengan dist[i][j] sebagai biaya terbaik yang diketahui dari i ke j. Mulailah dengan sisi langsung yang diberikan kepada Anda.
dist = [[INF] * n for _ in range(n)]Atur Diagonal
Setiap simpul dapat mencapai dirinya sendiri tanpa biaya, jadi atur diagonal dist[i][i] menjadi nol sebelum mulai melakukan relaksasi.
for i in range(n):
dist[i][i] = 0Gagasan Simpul Perantara
Triknya adalah mengizinkan jalur melewati simpul perantara k, lalu memeriksa apakah rute melalui k lebih murah daripada rute langsung.
Urutan Perulangan Penting
Perulangan terluar adalah k, yaitu titik tengah yang dipilih. Perulangan dalam i dan j mencoba setiap pasangan terhadap titik tengah tersebut.
for k in range(n):
for i in range(n):
for j in range(n):Langkah Relaksasi
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.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]Mengapa k Berada di Luar
Ketika pemrosesan k selesai, semua pasangan dapat menggunakan simpul perantara hingga k. Menempatkan k di perulangan terluar menjaga agar jaminan tersebut tetap benar.
Sisi Negatif Tidak Masalah
Floyd-Warshall menerima sisi negatif, tetapi tidak menerima siklus negatif. Siklus negatif membuat beberapa entri diagonal bernilai kurang dari nol.
Waktu Berjalan
Tiga perulangan atas n simpul menghasilkan waktu O(n^3) dan memori O(n^2), sehingga praktis hanya ketika n berjumlah beberapa ratus.
Kapan Memilihnya
Pilih Floyd-Warshall ketika graf berukuran kecil dan padat dan Anda benar-benar memerlukan jarak untuk setiap pasangan, bukan hanya dari satu sumber.
Pemeriksaan Singkat
Perulangan mana yang harus menjadi perulangan terluar dalam Floyd-Warshall?
Rekapitulasi: Floyd-Warshall
Inisialisasikan matriks, nolkan diagonal, lalu lakukan perulangan k, i, j dan relaksasikan melalui k. Jalur terpendek semua pasangan dalam O(n^3). 🧮
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Floyd-Warshall untuk Semua Pasangan” gratis?
Ya — teks lengkap “Floyd-Warshall untuk Semua Pasangan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Floyd-Warshall untuk Semua Pasangan”?
Jalur terpendek antara setiap pasangan Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Floyd-Warshall untuk Semua Pasangan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Dijkstra dengan Heap
- 0-1 BFS dengan Deque
- Bellman-Ford & Sisi Negatif
- Floyd-Warshall untuk Semua Pasangan