Problem ganda dari Max Flow adalah Min Cut, yaitu dengan mencari aliran maksimum s-t dari G, kita juga sekaligus menemukan potongan terkecil s-t dari G, yaitu himpunan edge dengan bobot minimum yang harus dbuang dari G sehingga tidak ada lagi jalur dari s ke t di G.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
Masalah Max-Flow (atau Min-Cut) muncul dalam beberapa aplikasi, seperti,
- Masalah terkait transportasi (apa cara terbaik untuk mengirimkan barang dari s (mungkin sebuah pabrik) ke t (mungkin sebuah distributor)
- Masalah terkait penyerangan jaringan (sabotasi/hancurkan beberapa sisi untuk memutuskan dua titik penting s dan t)
- Pencocokan (Bipartit) dan masalah Penugasan (yang juga mempunyai algoritma spesifik, lihatlah visualisasi Pencocokan Graf
- Prospek tim olahraga
- Segmentasi gambar, dll...
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
Halaman visualisasi ini akan menunjukkan eksekusi dari algoritma Aliran Maks (Max Flow) yang berjalan dalam graf flow (residu).
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
Masukan untuk algoritma Max Flow adalah graf flow (graf berarah berbobot G = (V, E) di mana bobot sisi e mewakili kapasitas c(e) (satuannya tergantung pada masalah, misalnya, liter/detik, orang/jam, dll) dari aliran yang dapat melewati sisi tersebut) dengan dua simpul yang dibedakan: simpul source s (dengan in-degree 0) dan simpul sink/tujuan/target t (dengan out-degree 0). Graf flow biasanya terhubung s-t, yaitu, ada setidaknya satu jalur dari s ke t (jika tidak, aliran maksimum secara trivial adalah 0).
Dalam visualisasi ini, dua input tambahan dari s (biasanya simpul 0) dan t (biasanya simpul V-1) diminta sebelum eksekusi algoritma Max Flow yang dipilih dan dapat disesuaikan oleh pengguna.
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
Keluaran dari algoritma Max Flow adalah nilai flow maksimum dan penugasan flow f pada setiap sisi yang memenuhi dua batasan penting:
- Batasan kapasitas (aliran pada setiap sisi (f(e)) berada antara 0 dan kapasitas (unit)nya (c(e)), yaitu, 0 ≤ f(e) ≤ c(e) — tidak negatif dan tidak lebih dari kapasitas), dan
- Batasan kesetimbangan (untuk setiap simpul kecuali s dan t, flow masuk = flow keluar)
Dalam visualisasi ini, kita fokus menunjukkan nilai flow maksimum terakhir dan komponen ST-min cut akhir pada akhir setiap eksekusi algoritma aliran maksimum, daripada penugasan tepat aliran f pada setiap sisi, yaitu, f(e) harus dihitung secara manual dari kapasitas awal c(e) (bingkai pertama dari animasi) dikurangi kapasitas residual akhir dari sisi e (bingkai terakhir dari animasi). Fitur yang hilang ini kemungkinan akan ditambahkan pada iterasi berikutnya dari halaman visualisasi ini.
Diskusi: Adakah cara lain untuk menghitung nilai aliran value(f)?
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
n Pada awal tiga algoritma Max Flow yang dibahas dalam visualisasi ini (metode Ford-Fulkerson, algoritma Edmonds-Karp, dan algoritma Dinic), graf flow awal dikonversi menjadi graf residual (dengan potensi penambahan sisi flow balik dengan kapasitas awal nol).
Sisi-sisi dalam graf residual menyimpan kapasitas sisa dari sisi-sisi tersebut yang dapat digunakan oleh aliran-aliran di masa depan. Pada awalnya, kapasitas sisa ini sama dengan kapasitas asli seperti yang ditentukan dalam graf aliran input.
Algoritma Max Flow akan mengirimkan flow untuk menggunakan beberapa (atau semua) dari kapasitas yang tersedia ini, secara iteratif.
Setelah kapasitas sisa dari suatu sisi mencapai 0, sisi tersebut tidak lagi dapat menerima aliran tambahan. Di masa mendatang, kami akan memperbarui visualisasi ini sehingga setiap sisi dalam graf residual yang memiliki kapasitas 0 (termasuk nol awal dari sisi aliran balik) tidak ditampilkan dalam visualisasi.
Ada tiga sumber berbeda untuk menspesifikasikan graf masukan:
- Gambar Graf: Anda dapat menggambar graf berarah dan berbobot apapun dengan simpul 0 sebagai simpul sumber default (sisi kiri dari layar) dan simpul V-1 sebagai simpul akhiran default (sisi kanan dari layar).
- Modeling: Banyak problem graf yang dapat direduksi menjadi masalah aliran maks. Di visualisasi ini, kami telah menyediakan contoh-contoh modeling untuk masalah Pencocokan Bipartit dengan Kardinalitas Maksimum (Maximum Cardinality Bipartite Matching, MCBM), masalah Rook Attack(tidak tersedia saat ini), dan masalah Baseball Elimination (tidak tersedia saat ini).
- Graf-Graf Contoh: Anda dapat memilih dari daftar graf-graf contoh pilihan kami untuk memulai.
Terdapat tiga algoritma Max Flow berbeda dalam visualisasi ini:
- Metode Ford-Fulkerson yang pelan O(mf × E),
- Algoritma Edmonds-Karp O(V × E^2) Edmonds-Karp, atau
- Algoritma Dinic O(V^2 × E).
Terdapat beberapa algoritma max flow lainnya, tetapi mereka masih belum ada dalam visualisasi ini.
Untuk tiga algoritma Max Flow yang dibahas dalam visualisasi ini, flow berturut-turut dikirim dari simpul source s ke simpul sink t melalui jalur augmentasi yang tersedia (jalur augmentasi adalah jalur dari s ke t yang melewati sisi-sisi dengan kapasitas residual positif (c(e)-f(e)) yang tersisa).
Ketiga algoritma Max Flow dalam visualisasi ini memiliki perilaku berbeda dalam cara mereka menemukan jalur augmentasi.
Namun, semua tiga algoritma Max Flow dalam visualisasi ini berhenti ketika tidak ada lagi jalur augmentasi yang mungkin dan melaporkan nilai flow maksimum (dan penugasan flow pada setiap sisi dalam graf flow).
Nanti kita akan membahas bahwa nilai flow maksimum ini juga merupakan nilai potongan minimum dari graf flow (Teorema Max-Flow/Min-Cut yang terkenal itu).
mulai dari 0 flow
while terdapat jalur augmentasi: // algoritma iteratif
cari jalur augmentasi (untuk sekarang, sembarang graf travesal bisa)
hitung bottleneck kapasitas
tambahkan flow pada jalur sebanyak kapasitas bottleneck
Teorema terkenal ini menyatakan bahwa dalam jaringan aliran, aliran maksimum (max flow) dari s ke t sama dengan total bobot sisi-sisi dalam pemotongan minimum (min cut), yaitu total bobot sisi-sisi terkecil yang harus dihilangkan untuk memutuskan hubungan s dari t.
Dalam kelas Ilmu Komputer yang khas, dosen biasanya akan meluangkan waktu untuk menjelaskan teorema ini dengan benar (menjelaskan apa itu st-cut, kapasitas st-cut, aliran bersih melintasi st-cut yang sama dengan penugasan aliran f saat ini yang tidak akan melebihi kapasitas pemotongan, dan akhirnya Teorema Max-Flow/Min-Cut). Untuk visualisasi ini, kami hanya mengambil pernyataan ini apa adanya.
Diskusi: Untuk kelas nyata di NUS, kami sebenarnya akan membahas teorema-teorema ini.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
Menggunakan Teorema Max-Flow/Min-Cut, kita kemudian dapat membuktikan bahwa flow f adalah maxflow jika dan hanya jika tidak ada (lagi) jalur augmentasi yang tersisa dalam graf residual.
Karena inilah yang dilakukan oleh Metode Ford-Fulkerson, kita dapat menyimpulkan kebenaran dari Metode Ford-Fulkerson ini, yaitu, jika Metode Ford-Fulkerson berakhir, maka tidak ada jalur augmentasi yang tersisa dan dengan demikian flow yang dihasilkan adalah maksimum (dan kita juga dapat membangun Min-Cut yang setara, pada slide berikutnya).
Kita bisa membangun sisi-sisi dalam Min-Cut sebagai berikut:
- Jalankan Ford-Fulkerson (atau algoritma MaxFlow lainnya) sampai selesai.
- Misalkan S merupakan himpunan simpul yang masih bisa dicapai dari source s.
Kita jalankan DFS (atau BFS) dalam graf residu dari source s.
Semua simpul yang masih dicapai berada di S.
Misalkan T merupakan himpunan simpul sisanya T = V \\ S. - Untuk semua sisi dalam S, cek semua sisi yang keluar:
Jika sisi keluar dari S (dan masuk T), tambahkan sisi ini ke min-cut.
Jika kedua titik akhir sisi berada dalam S, lanjutkan
Itu saja, (S,T) adalah sebuah st-cut, sisi dari (S → T) adalah perpotongan minimum (mincut), dan aliran yang melalui perpotongan minimum (S,T) adalah semaksimum mungkin.
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
Metode Ford-Fulkerson selalu berakhir jika kapasitanya adalah bilangan bulat.
Ini karena setiap iterasi metode Ford-Fulkerson selalu menemukan jalur augmentasi baru dan setiap jalur augmentasi harus memiliki kapasitas bottleneck minimal 1 (karena batasan bilangan bulat tersebut). Oleh karena itu, setiap iterasi meningkatkan aliran dari setidaknya satu sisi minimal 1, membawa Ford-Fulkerson lebih dekat ke penghentian.
Karena jumlah sisi adalah terbatas (begitu juga dengan kapasitas maksimum per sisi), ini menjamin penghentian metode Ford-Fulkerson ketika max flow mf tercapai dan tidak ada lagi jalur augmentasi yang tersisa.
Dalam kasus terburuk, metode Ford-Fulkerson berjalan selama mf iterasi, dan setiap kali menggunakan O(E) DFS. Waktu berjalan keseluruhan kira-kira adalah O(mf × E) — ini sebenarnya tidak diinginkan terutama jika nilai mf adalah angka yang sangat besar.
Diskusi: Bagaimana jika kapasitasnya adalah bilangan rasional? Bagaimana jika kapasitasnya adalah bilangan floating-point?
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
Implementasi: Pertama, kita mengabaikan kapasitas dari sisi-sisi terlebih dahulu (anggap semua sisi dalam graf residual memiliki bobot 1), dan kita menjalankan BFS O(E) untuk menemukan jalur augmentasi terpendek (dalam hal jumlah sisi yang digunakan). Segala sesuatu lainnya sama seperti Metode Ford-Fulkerson dasar yang diuraikan sebelumnya.
Dapat dibuktikan bahwa Edmonds-Karp akan menggunakan paling banyak O(VE) iterasi sehingga berjalan paling lama dalam waktu O(VE * E) = O(VE^2).
The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.
If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.
FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.
Pada saat anda mengerjakan masalah Max Flow (atau Min Cut), kita tidak perlu menciptakan roda tiap kali.
Anda dapat menggunakan/memodifikasi kode implementasi kami untuk algoritma Max Flow (Edmonds-Karp/Dinic): maxflow.cpp | py | java | ml.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Visualisation Scale
Toggle V. Number for 0.5x
Ubah Graf
Modeling
Graf-Graf Contoh
Ford-Fulkerson
Edmonds-Karp
Dinic
Min-Cost-Max-Flow