Dinic's algorithm

From Wikipedia, the free encyclopedia

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 Dinitz.^[2] The algorithm runs in $O(V^{2}E)$ time and is similar to the Edmonds–Karp algorithm, which runs in $O(VE^{2})$ 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.

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\times V\to R^{+}$ defined as,

if $(u,v)\in E$ ,
$c_{f}(u,v)=c(u,v)-f(u,v)$

$c_{f}(v,u)=f(u,v)$
$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)\in V\times V:c_{f}(u,v)>0\}$ .

An augmenting path is an $s-t$ path in the residual graph $G_{f}$ .

Define $\operatorname {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)\in E_{f}:\operatorname {dist}(v)=\operatorname {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.

Set $f(e)=0$ for each $e\in E$ .
Construct $G_{L}$ from $G_{f}$ of $G$ . If $\operatorname {dist}(t)=\infty$ , stop and output $f$ .
Find a blocking flow $f\;'$ in $G_{L}$ .
Augment flow $\ f$ by $f\;'$ and go back to step 2.

Analysis

It can be shown that the number of edges 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(VE)$ 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(VE\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({\sqrt {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({\sqrt {V}})$ , therefore leading to the $O({\sqrt {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.^[3]

Example

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

	$G$	$G_{f}$	$G_{L}$
1.
	The blocking flow consists of $\{s,1,3,t\}$ with 4 units of flow, $\{s,1,4,t\}$ with 6 units of flow, and $\{s,2,4,t\}$ with 4 units of flow. Therefore the blocking flow is of 14 units and the value of flow $\|f\|$ is 14. Note that each augmenting path in the blocking flow has 3 edges.
2.
	The blocking flow consists of $\{s,2,4,3,t\}$ with 5 units of flow. Therefore the blocking flow is of 5 units and the value of flow $\|f\|$ is 14 + 5 = 19. Note that each augmenting path has 4 edges.
3.
	Since $t$ cannot be reached in $G_{f}$ . 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.

History

Dinic's algorithm was published in 1970 by former Russian Computer Scientist Yefim (Chaim) A. Dinitz, who is today a member of the Computer Science department at Ben-Gurion University of the Negev (Israel), earlier than the Edmonds–Karp algorithm, which was published in 1972 but was discovered earlier. They 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.

Notes

↑ Verheest, Frank (2000). "Plasmas as the fourth state of matter". Waves in Dusty Space Plasmas. Norwell MA: Kluwer Academic. p. 1. ISBN 0-7923-6232-2.
↑ Yefim Dinitz (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Doklady Akademii nauk SSSR 11: 1277–1280.
↑ Tarjan 1983, p. 102.

References

Yefim Dinitz (2006). "Dinitz' Algorithm: The Original Version and Even's Version". In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman. Theoretical Computer Science: Essays in Memory of Shimon Even. Springer. pp. 218–240. ISBN 978-3-540-32880-3.
Tarjan, R. E. (1983). Data structures and network algorithms.
B. H. Korte, Jens Vygen (2008). "8.4 Blocking Flows and Fujishige's Algorithm". Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 174–176. ISBN 978-3-540-71844-4.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.