Lesson 6

The step of the algorithm (increasing the flow) consists of choosing a path from source to sink in the residual network. Such a path can be found, for example, by breadth-first search, and once it is found, we increase the flow along it as much as possible (the limiting factor is the edge with the smallest capacity in the residual network). If there are no paths from \(s\) to \(t\) in the residual network, the algorithm stops.

For example, for the flow

It is easy to see that in the case of integer capacities this algorithm will stop sooner or later: at each step the flow increases by at least one (in the general case this is not true). However, we still haven’t proven that our algorithm always finds the optimal flow. We’ll prove that in the next section.