Maximum FlowLesson 42Free preview

DSA Ford-Fulkerson

This lesson is part of DSA · All levels

Summary

Ford-Fulkerson calculated maximum flow by continuously finding an augmenting path from source to destination and then adding the current to the capacity of the remaining path. The process repeats until there's no augmenting path left. When the capacity is an integer, the algorithm will stop, but the complexity depends on the capacity value.

Key points

Repeat: find the augmenting path, add the minimum current of that path.
Manage the residual graph with the forward and back edges
Stop when there's no augmenting path left
Complexity depends on the size of the capacity,

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.