en>Helpful Pixie Bot: ISBNs (Build KH)

2012-05-12T01:05:35Z

ISBNs (Build KH)

New page

'''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]].<ref>{{cite journal | author = [[Yefim Dinitz]] | title = Algorithm for solution of a problem of maximum flow in a network with power estimation | journal = Doklady Akademii nauk SSSR | volume = 11 | year = 1970 | pages = 1277–1280 | url=http://www.cs.bgu.ac.il/~dinitz/D70.pdf}}</ref> The algorithm runs in <math>O(V^2 E)</math> time and is similar to the [[Edmonds–Karp algorithm]], which runs in <math>O(VE^2)</math> 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 <math>G = ((V,E),c,s,t)</math> be a network with <math>c(u,v)</math> and <math>f(u,v)</math> the capacity and the flow of the edge <math>(u,v)</math> respectively.

:The '''residual capacity''' is a mapping <math>c_f : V\times V \to R^+</math> defined as,
:# if <math>(u,v)\in E</math>,
:#: <math>c_f(u,v) = c(u,v) - f(u,v) </math>
:#: <math>c_f(v,u) = f(u,v)</math>
:# <math>c_f(u,v) = 0</math> otherwise.

:The '''residual graph''' is the graph <math>G_f = ((V, E_f), c_f|_{E_f}, s, t)</math>, where
:: <math>E_f = \{(u,v)\in V \times V : c_f(u,v) > 0\}</math>.

:An '''augmenting path''' is an <math>s-t</math> path in the residual graph <math>G_f</math>.

:Define <math>\operatorname{dist}(v)</math> to be the length of the shortest path from <math>s</math> to <math>v</math> in <math>G_f</math>. Then the '''level graph''' of <math>G_f</math> is the graph <math>G_L = (V, E_L, c_f|_{E_L}, s,t)</math>, where
:: <math>E_L = \{(u,v)\in E_f : \operatorname{dist}(v) = \operatorname{dist}(u) + 1\}</math>.

:A '''blocking flow''' is an <math>s-t</math> flow <math>f</math> such that the graph <math>G' = (V,E_L', s, t)</math> with <math>E_L' = \{(u,v) : f(u,v) < c_f|_{E_L}(u,v)\}</math> contains no <math>s-t</math> path.

==Algorithm==
'''Dinic's Algorithm'''
: ''Input'': A network <math>G = ((V, E), c, s, t)</math>.
: ''Output'': An <math>s-t</math> flow <math>f</math> of maximum value.
# Set <math>f(e) = 0</math> for each <math>e\in E</math>.
# Construct <math>G_L</math> from <math>G_f</math> of <math>G</math>. If <math>\operatorname{dist}(t) = \infty</math>, stop and output <math>f</math>.
# Find a blocking flow <math>f\;'</math> in <math>G_L</math>.
# Augment flow <math>\ f</math> by <math>f\;'</math> 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 <math>n-1</math> blocking flows in the algorithm, where <math>n</math> is the number of vertices in the network. The level graph <math>G_L</math> can be constructed by [[Breadth-first search]] in <math>O(E)</math> time and a blocking flow in each level graph can be found in <math>O(VE)</math> time. Hence, the running time of Dinic's algorithm is <math>O(V^2 E)</math>.

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

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

In networks arising during the solution of [[bipartite matching]] problem, the number of phases is bounded by <math>O(\sqrt{V})</math>, therefore leading to the <math>O(\sqrt{V} E)</math> 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.{{sfn|Tarjan|1983|p=102}}

==Example==
The following is a simulation of the Dinic's algorithm. In the level graph <math>G_L</math>, the vertices with labels in red are the values <math>\operatorname{dist}(v)</math>. The paths in blue form a blocking flow.

{| class="wikitable" style="text-align:center; width:915px;" border="1"
|-
! width="15px" |

! <math>G</math>
! <math>G_f</math>
! <math>G_L</math>
|-
! 1.
| [[File:Dinic algorithm G1.svg|300px]]
| [[File:Dinic algorithm Gf1.svg|300px]]
| [[File:Dinic algorithm GL1.svg|300px]]
|-
|
| align="left" colspan="3" |
The blocking flow consists of
# <math>\{s, 1, 3, t\}</math> with 4 units of flow,
# <math>\{s, 1, 4, t\}</math> with 6 units of flow, and
# <math>\{s, 2, 4, t\}</math> with 4 units of flow.
Therefore the blocking flow is of 14 units and the value of flow <math>|f|</math> is 14. Note that each augmenting path in the blocking flow has ''3'' edges.
|-
! 2.
| [[File:Dinic algorithm G2.svg|300px]]
| [[File:Dinic algorithm Gf2.svg|300px]]
| [[File:Dinic algorithm GL2.svg|300px]]
|-
|
| align="left" colspan="3" |
The blocking flow consists of
# <math>\{s, 2, 4, 3, t\}</math> with 5 units of flow.
Therefore the blocking flow is of 5 units and the value of flow <math>|f|</math> is 14 + 5 = 19. Note that each augmenting path has 4 edges.
|-
! 3.
| [[File:Dinic algorithm G3.svg|300px]]
| [[File:Dinic algorithm Gf3.svg|300px]]
| [[File:Dinic algorithm GL3.svg|300px]]
|-
|
| align="left" colspan="3" |
Since <math>t</math> cannot be reached in <math>G_f</math>. 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.

==See also==
* [[Ford–Fulkerson algorithm]]
* [[Maximum flow problem]]

== Notes ==
{{reflist}}

==References==
* {{cite book | author = Yefim Dinitz | editor = [[Oded Goldreich]], Arnold L. Rosenberg, and Alan L. Selman | title = Theoretical Computer Science: Essays in Memory of [[Shimon Even]] | chapter = Dinitz' Algorithm: The Original Version and Even's Version | year = 2006 | publisher = Springer | isbn = 978-3-540-32880-3 | pages = 218–240 | url = http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf}}
* {{cite book | ref=harv | last=Tarjan | first=R. E. |year =1983 | title=Data structures and network algorithms }}
* {{cite book | author = B. H. Korte, Jens Vygen | title = Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21) | chapter = 8.4 Blocking Flows and Fujishige's Algorithm | year = 2008 | publisher = Springer Berlin Heidelberg | isbn = 978-3-540-71844-4 | pages = 174–176}}

[[Category:Network flow]]
[[Category:Graph algorithms]]

Smooth functor - Revision history

en>Helpful Pixie Bot: ISBNs (Build KH)