Finding maximal flow in a transportation network

1 Formulation of the problem

A transportation network is a directed graph $G = (V, E)$ in which a nonnegative capacity $c(e) \ge 0$ is assigned to each edge $e \in E$. We assume that, along with each edge $e = (v, w) \in E$, the graph also contains the reverse edge $e^R = (w, v)$ (to which, if required, the zero capacity is assigned).

Let two vertices of a graph $G$ be marked, namely, the source $s$ and the sink $t$. It can be assumed without loss of generality that all the other vertices lie on a path from $s$ to $t$. A flow is a function $f: E \to \mathbb{R}$ that satisfies the following requirements:

• capacity constraint: $f(e) \le c(e)$;
• antisymmetry: $f(e^R) = -f(e)$;
• flow conservation law:

$\forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e).$

The value of flow is the total amount of flow from the source:

$\left \vert f \right \vert = \sum_{e = (s, v)} f(e).$

Maximal flow problem in a transportation network. It is required to find a flow with maximum value:

$\left \vert f \right \vert \to \max.$

2 Properties of the problem

The total flow out of the source is equal to the total flow into the sink:

$\forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e).$

(To prove this statement, it suffices to add up the flow conservation relations for all the vertices except for the source and sink.)

3 Variants of the problem

Depending on constraints on the capacity, the following cases may be distinguished:

• arbitrary positive capacity;
• integral capacity;
• unit capacity (in this case, the maximal flow is equal to the edge connectivity of the graph).

4 Algorithms for solving the problem

• The Ford-Fulkerson algorithm and its versions with the complexity $O(n^2m)$ (for Dinic's algorithm). In the case of integral capacity bounded by $K$, the complexity is $O(Km)$.
• The preflow push algorithm The complexity is $O(mn \ln n)$ (provided that Sleator-Tarjan dynamic trees are used ).

Notation: $m$ is the number of edges, $n$ is the number of vertices.