For previous types of problems, we required new algorithms for every new problem.
For network flow problems, we use the same algorithm every single time, but apply new modifications to the input.
Network flow allow us to solve 2 problems at once; the Max flow and Min cut problems:
All kinds of applications:
All of these can be solved by using just one algorithm, which we will look at it today.
Maximum flow problems try to, as the name suggest, maximize the flow. But what is that?
You can understand flow as an abstract entity flowing through a directed graph, generated at a source $s$, transmitted across edges, and absorbed in a sink $t$. Every edge has a (nonnegative) capacity $c(e)$. Note that we assume (for now) that there are no parallel edges, no edge enters $s$ nor leaves $t$.
We want to solve the problem of the maximum flow of a given graph. For example, what is the maximum flow from $s$ to $t$?
