Maximum FlowLesson 41Preview gratis
DSA Maximum Flow
Lesson ini bagian dari DSA · Semua level
Ringkasan
Masalah maximum flow mencari nilai arus maksimum yang dapat dikirim dari sumber ke tujuan pada jaringan berbobot yang disebut flow network. Konsep kuncinya adalah augmenting path dan residual capacity: selama masih ada jalur dengan kapasitas sisa positif, arus dapat ditingkatkan. Teorema max-flow min-cut memastikan arus maksimum sama dengan kapasitas minimum pemotongan.
Poin kunci
- Flow network terdiri dari sumber, tujuan, dan sisi berkapasitas
- Augmenting path adalah jalur dengan kapasitas sisa positif
- Nilai arus maksimum sama dengan kapasitas minimum cut (max-flow min-cut)
- Ford-Fulkerson dan Edmonds-Karp adalah algoritma penerapannya
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.