- Titik singgah saat ini
- Sudah jadi titik singgah
- Pasangan dipersingkat
- Jalur
Algoritma Floyd–Warshall
Seberapa jauh dari setiap kota ke setiap kota lain? Floyd–Warshall menjawabnya sekaligus, dengan sebuah tabel dan tiga perulangan bersarang. Setiap putaran mengizinkan satu simpul lagi sebagai titik singgah di jalan dan memeriksa, untuk setiap pasangan, apakah memutar lewat simpul itu lebih pendek. Jalankan langkah demi langkah untuk melihat tabel terisi dan jarak-jaraknya turun. Tekan Putar untuk melihat tabel terisi, atau Langkah dan Mundur untuk maju satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja. Tabel berisi jarak terpendek yang ditemukan sejauh ini antara setiap pasangan simpul; angka di tiap sisi adalah panjangnya. Setiap putaran mengizinkan satu simpul lagi sebagai titik singgah di jalan, dan setiap langkah menunjukkan pasangan yang menjadi lebih pendek lewat simpul itu. Klik simpul untuk menjadikannya awal; ubah klik ke Tujuan lalu klik simpul lain untuk melihat jalur terpendek di antara keduanya di akhir. Graf baru membuat graf lain; pilih berapa simpul dan sisinya. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Tekan Putar, atau pakai Langkah dan Mundur untuk bergerak satu langkah demi satu langkah. Geser penggeser langkah untuk melompat ke mana saja.
- Perhatikan tabel: baris dan kolom titik singgah saat ini diwarnai, dan setiap langkah menulis jarak yang lebih pendek.
- Pilih awal dan tujuan untuk melihat jalur terpendek di antara keduanya di akhir. Graf baru membuat graf lain untuk dicoba.
Cara kerja Floyd–Warshall
Buat tabel dengan satu baris dan satu kolom per simpul. Isi 0 di diagonal, panjang sisi di tempat dua simpul terhubung, dan tak hingga di tempat lain. Lalu ambil setiap simpul k bergiliran sebagai calon titik singgah. Untuk setiap pasangan i, j, bandingkan jarak dari i ke j di tabel dengan jarak dari i ke k ditambah jarak dari k ke j, dan simpan yang lebih kecil. Setelah simpul terakhir, setiap entri adalah jarak terpendek antara kedua simpulnya.
Mengapa ini benar
Setelah putaran k, tabel berisi, untuk setiap pasangan, jalur terpendek yang semua titik singgahnya termasuk simpul yang sudah ditangani. Putaran simpul berikutnya hanya perlu memutuskan apakah simpul itu membantu: jalur terpendek lewat simpul itu adalah jalur terpendek ke sana ditambah jalur terpendek dari sana, dan keduanya sudah ada di tabel. Cara membangun jawaban besar dari jawaban kecil yang sudah ditemukan ini disebut pemrograman dinamis. Dengan sisi negatif, cara ini tetap berhasil, dan angka negatif di diagonal menunjukkan adanya siklus negatif.
Pertanyaan yang sering diajukan
Apa itu algoritma Floyd–Warshall?
Algoritma yang mencari jarak terpendek antara setiap pasangan simpul dalam graf berbobot. Algoritma ini menyimpan tabel jarak dan, untuk tiap simpul secara bergiliran, memeriksa apakah lewat simpul itu membuat suatu pasangan lebih pendek.
Seberapa cepat Floyd–Warshall?
Ada tiga perulangan bersarang atas n simpul, jadi kerjanya tumbuh sebanding n³, dan tabel butuh n² entri. Itu cukup untuk graf dengan beberapa ratus simpul. Untuk graf besar yang jarang, menjalankan algoritma Dijkstra dari setiap simpul lebih cepat.
Bisakah Floyd–Warshall menangani sisi negatif?
Bisa, selama tidak ada siklus negatif. Jika ada, suatu entri di diagonal menjadi negatif, dan dengan cara itulah Floyd–Warshall mendeteksinya.
Bagaimana mendapatkan jalurnya, bukan hanya jaraknya?
Simpan tabel kedua berisi simpul berikutnya di jalan dari i ke j. Setiap kali suatu pasangan menjadi lebih pendek lewat k, salin simpul berikutnya dari i menuju k. Mengikuti tabel itu dari i ke j akan menyusun jalurnya.
Apakah graf saya dikirim ke mana pun?
Tidak. Graf dibuat dan tabel diisi di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor