Maximum flow and minimum cut problem, Ford–Fulkerson algorithm


Maximum flow problem

Maximum flow promlem is a problem that maximizes the flow from the source to the sink in the network consisting of paths with capacity. It is necessary not to exceed the capacity and to equal input and output amount for each node. Besides, all of the data emitted from the source must be sent to the sink.

Minimum cut problem

Minimum cut problem is a problem that minimizes capacity of cut that divides the source and the sink. Cut (S,V\S) is a set of outgoing paths of the nodes’ subset S⊆V and cut capacity is the total capacity of the edges.

Ford–Fulkerson algorithm

if there are paths from the source to the sink, it increases the flow as much as possible and adds inverse paths with capacity same as the value having increased. Repeat this until there are no more paths. The graph of paths with remaining capacity is called a residual graph.

If maximum flow is F, time complexity is O(F|E|) but it is unlikely that the maximum flow can be updated only one by one, so it is not so slow.


Let S be a subset of the nodes reachable from the source and V be a residual graph that the algorithm is completed. (S,V\S) is a cut dividing the source and the sink. V doesn’t contain paths from the source to the sink so capacity of the paths from S to V\S is used completely and paths from V\S to S is not used. Flow can’t be bigger than the cut capacity so this is the maximum flow.

And a match between the maximum flow and the minimum cut is also derived. This is Max-flow min-cut theorem and it can be said that minimum cut is the bottleneck.


数理手法III (数理最適化) 第8回 ネットワーク最適化 最大流問題と増加路アルゴリズム

プログラミングコンテストチャレンジブック [第2版]