Maximum FlowLesson 43Free preview

DSA Edmonds-Karp

This lesson is part of DSA · All levels

Summary

Edmonds-Karp is a Ford-Fulkerson refinement that always chooses the shortest path augmenting using BFS. Thus its complexity becomes limited and no longer depends on the size of the capacity. This approach is more stable and often becomes a practical option for calculating maximum flow.

Key points

Using BFS to select the shortest augmenting path
Complexity is finite
Not affected by the large capacity values like the Ford-Fulkerson
Both residual-based graphs and augmenting paths

Full lesson

Code examples and quizzes

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