Maximum FlowLesson 42Preview gratis
DSA Ford-Fulkerson
Lesson ini bagian dari DSA · Semua level
Ringkasan
Ford-Fulkerson menghitung maximum flow dengan terus menemukan augmenting path dari sumber ke tujuan lalu menambah arus sebesar kapasitas sisa jalur tersebut. Proses berulang hingga tidak ada augmenting path tersisa. Bila kapasitas berbilangan bulat, algoritma ini pasti berhenti, namun kompleksitasnya bergantung pada nilai kapasitas.
Poin kunci
- Berulang: cari augmenting path, tambah arus minimal jalur itu
- Mengelola residual graph dengan sisi maju dan back edge
- Berhenti bila tidak ada augmenting path tersisa
- Kompleksitas bergantung besar kapasitas, O(E * max_flow)
Materi lengkap
Contoh kode dan kuis
Materi lengkap, contoh kode, dan kuis tersedia untuk pelanggan. 5 soal.