I’m trying to learn augmenting paths and I got confused. I’ve found some other source that has the same setup that my slides have, therefore I will refer to that.
It is said that
Each augmenting path computation can be easily done in O(m) time.
in these lecture notes within a graph of m edges. I could not understand how it is O(m). Isn’t trying to find an augmenting path that has capacity from source to the target an exhaustive process? Maybe I misunderstand what they mean as augmenting path computation but even if that is the case, the clarification of that would be helpful