Dinic's algorithm

History

Yefim Dinitz invented this algorithm in response to a pre-class exercise in Adel'son-Vel'sky's (co-inventor of AVL trees) Algorithm class. At the time he was not aware of the basic facts regarding Ford-Fulkerson algorithm.

Dinitz mentions inventing his algorithm in January 1969, which was published in 1970 in journal Doklady Akademii nauk SSSR. In 1974, Shimon Even and (his then Ph.D. student) Alon Itai at the Technion in Haifa were very curious and intrigued by the Dinitz's algorithm as well as Alexander Karzanov's idea of blocking flow. However it was hard to decipher these two papers for them, each being limited to four pages to meet the restrictions of journal Doklady Akademii nauk SSSR. However Even did not give up and after three days of effort managed to understand both papers except for the layered network maintenance issue. Over the next couple of years, Even gave lectures on "Dinic's algorithm" mispronouncing the name of the author while popularizing it. Even and Itai also contributed to this algorithm by combining BFS and DFS, which is the current version of algorithm

For about 10 years of time after Ford–Fulkerson algorithm was invented, it was unknown if it can be made to terminate in polynomial time in the generic case of irrational edge capacities. This caused lack of any known polynomial time algorithm that solved max flow problem in generic case. Dinitz algorithm and the Edmonds–Karp algorithm, which was published in 1972, independently showed that in the Ford–Fulkerson algorithm, if each augmenting path is the shortest one, the length of the augmenting paths is non-decreasing and it always terminated.

Definition

Let G = ( ( V , E ) , c , s , t ) be a network with c ( u , v ) and f ( u , v ) the capacity and the flow of the edge ( u , v ) respectively.

The residual capacity is a mapping c f : V × V → R + defined as,

1. if ( u , v ) ∈ E , c f ( u , v ) = c ( u , v ) − f ( u , v ) c f ( v , u ) = f ( u , v )
2. c f ( u , v ) = 0 otherwise.

The residual graph is the graph G f = ( ( V , E f ) , c f | E f , s , t ) , where E f = { ( u , v ) ∈ V × V : c f ( u , v ) > 0 } .An augmenting path is an s − t path in the residual graph G f .Define dist ⁡ ( v ) to be the length of the shortest path from s to v in G f . Then the level graph of G f is the graph G L = ( V , E L , c f | E L , s , t ) , where E L = { ( u , v ) ∈ E f : dist ⁡ ( v ) = dist ⁡ ( u ) + 1 } .A blocking flow is an s − t flow f such that the graph G ′ = ( V , E L ′ , s , t ) with E L ′ = { ( u , v ) : f ( u , v ) < c f | E L ( u , v ) } contains no s − t path.

Algorithm

Dinic's Algorithm

Input: A network G = ( ( V , E ) , c , s , t ) .Output: An s − t flow f of maximum value.

1. Set f ( e ) = 0 for each e ∈ E .
2. Construct G L from G f of G . If dist ⁡ ( t ) = ∞ , stop and output f .
3. Find a blocking flow f ′ in G L .
4. Augment flow   f by f ′ and go back to step 2.

Analysis

It can be shown that the number of layers in each blocking flow increases by at least 1 each time and thus there are at most n − 1 blocking flows in the algorithm, where n is the number of vertices in the network. The level graph G L can be constructed by Breadth-first search in O ( E ) time and a blocking flow in each level graph can be found in O ( V E ) time. Hence, the running time of Dinic's algorithm is O ( V 2 E ) .

Using a data structure called dynamic trees, the running time of finding a blocking flow in each phase can be reduced to O ( E log ⁡ V ) and therefore the running time of Dinic's algorithm can be improved to O ( V E log ⁡ V ) .

Special cases

In networks with unit capacities, a much stronger time bound holds. Each blocking flow can be found in O ( E ) time, and it can be shown that the number of phases does not exceed O ( E ) and O ( V 2 / 3 ) . Thus the algorithm runs in O ( min { V 2 / 3 , E 1 / 2 } E ) time.

In networks arising during the solution of bipartite matching problem, the number of phases is bounded by O ( V ) , therefore leading to the O ( V E ) time bound. The resulting algorithm is also known as Hopcroft–Karp algorithm. More generally, this bound holds for any unit network — a network in which each vertex, except for source and sink, either has a single entering edge of capacity one, or a single outgoing edge of capacity one, and all other capacities are arbitrary integers.

Example

The following is a simulation of Dinic's algorithm. In the level graph G L , the vertices with labels in red are the values dist ⁡ ( v ) . The paths in blue form a blocking flow.