Dinic's algorithm

From Wikipedia, the free encyclopedia
  (Redirected from Dinitz blocking flow algorithm)
Jump to: navigation, search

Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz.[1] The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance.

History[edit]

Yefim Dinitz invented this algorithm in response to a pre-class exercise in Adelson-Velsky's algorithms class. At the time he was not aware of the basic facts regarding the Ford–Fulkerson algorithm.[2]

Dinitz mentions inventing his algorithm in January 1969, which was published in 1970 in the 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 Dinitz's algorithm as well as Alexander Karzanov's idea of blocking flow. However it was hard for them to decipher these two papers, each being limited to four pages to meet the restrictions of journal Doklady Akademii nauk SSSR. 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 the algorithm.[3]

For about 10 years of time after the Ford–Fulkerson algorithm was invented, it was unknown if it could be made to terminate in polynomial time in the general case of irrational edge capacities. This caused a lack of any known polynomial-time algorithm to solve the max flow problem in generic cases. Dinitz's algorithm and the Edmonds–Karp algorithm (published in 1972) both independently showed that in the Ford–Fulkerson algorithm, if each augmenting path is the shortest one, then the length of the augmenting paths is non-decreasing the algorithm always terminates.

Definition[edit]

Let be a network with and the capacity and the flow of the edge respectively.

The residual capacity is a mapping defined as,
  1. if ,
  2. otherwise.
The residual graph is the graph , where
.
An augmenting path is an path in the residual graph .
Define to be the length of the shortest path from to in . Then the level graph of is the graph , where
.
A blocking flow is an flow such that the graph with contains no path.

Algorithm[edit]

Dinic's Algorithm

Input: A network .
Output: An flow of maximum value.
  1. Set for each .
  2. Construct from of . If , stop and output .
  3. Find a blocking flow in .
  4. Augment flow by and go back to step 2.

Analysis[edit]

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 blocking flows in the algorithm, where is the number of vertices in the network. The level graph can be constructed by breadth-first search in time, and a blocking flow in each level graph can be found in time. Hence, the running time of Dinic's algorithm is .

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

Special cases[edit]

In networks with unit capacities, a much stronger time bound holds. Each blocking flow can be found in time, and it can be shown that the number of phases does not exceed and . Thus the algorithm runs in time.[4]

In networks that arise from the bipartite matching problem, the number of phases is bounded by , therefore leading to the 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.[5]

Example[edit]

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

1. Dinic algorithm G1.svg Dinic algorithm Gf1.svg Dinic algorithm GL1.svg

The blocking flow consists of

  1. with 4 units of flow,
  2. with 6 units of flow, and
  3. with 4 units of flow.

Therefore, the blocking flow is of 14 units and the value of flow is 14. Note that each augmenting path in the blocking flow has 3 edges.

2. Dinic algorithm G2.svg Dinic algorithm Gf2.svg Dinic algorithm GL2.svg

The blocking flow consists of

  1. with 5 units of flow.

Therefore, the blocking flow is of 5 units and the value of flow is 14 + 5 = 19. Note that each augmenting path has 4 edges.

3. Dinic algorithm G3.svg Dinic algorithm Gf3.svg Dinic algorithm GL3.svg

Since cannot be reached in , the algorithm terminates and returns a flow with maximum value of 19. Note that in each blocking flow, the number of edges in the augmenting path increases by at least 1.

See also[edit]

Notes[edit]

  1. ^ Yefim Dinitz (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation" (PDF). Doklady Akademii nauk SSSR. 11: 1277–1280. 
  2. ^ Ilan Kadar; Sivan Albagli (2009-11-27). "Dinitz's algorithm for finding a maximum flow in a network". 
  3. ^ Yefim Dinitz. "Dinitz's Algorithm: The Original Version and Even's Version" (PDF). 
  4. ^ Even, Shimon; Tarjan, R. Endre (1975). "Network Flow and Testing Graph Connectivity". SIAM Journal on Computing. 4 (4): 507–518. doi:10.1137/0204043. ISSN 0097-5397. 
  5. ^ Tarjan 1983, p. 102.

References[edit]