Dinic's algorithm

Dinitz invented the algorithm in January 1969, as a master's student in Georgy Adelson-Velsky's group. A few decades later, he would recall:

{{blockquote

| text=In Adel'son-Vel'sky's Algorithms class, the lecturer had a habit of giving the problem to be discussed at the next meeting as an exercise to students. The DA was invented in response to such an exercise. At that time, the author was not aware of the basic facts regarding [the Ford–Fulkerson algorithm]….

⋮

Ignorance sometimes has its merits. Very probably, DA would not have been invented then, if the idea of possible saturated edge desaturation had been known to the author.

| multiline=yes

}}

In 1970, Dinitz published a description of the algorithm in 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 V. Karzanov's related 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 how the algorithm is now commonly presented.

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 and the algorithm always terminates.

Let $G\; =\; ((V,E),c,f,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\backslash colon\; V\backslash times\; V\; \backslash to\; R^+$ defined as,

:# if $(u,v)\backslash in\; E$,

:#: $c\_f(u,v)\; =\; c(u,v)\; -\; f(u,v)$

:# if $(v,u)\backslash in\; E$,

:#: $c\_f(u,v)\; =\; f(v,u)$

:# $c\_f(u,v)\; =\; 0$ otherwise.

:The residual graph is an unweighted graph $G\_f\; =\; ((V,\; E\_f),\; c\_f|\_\{E\_f\},\; s,\; t)$, where

:: $E\_f\; =\; \backslash \{(u,v)\backslash in\; V\; \backslash times\; V\; \backslash colon\backslash ;\; c\_f(u,v)\; >\; 0\backslash \}$.

:An augmenting path is an $s$–$t$ path in the residual graph $G\_f$.

:Define $\backslash 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\; =\; \backslash \{(u,v)\backslash in\; E\_f\; \backslash colon\backslash ;\; \backslash operatorname\{dist\}(v)\; =\; \backslash operatorname\{dist\}(u)\; +\; 1\backslash \}$.

:A blocking flow is an $s$–$t$ flow $f\text{'}$ such that the graph $G\text{'}\; =\; ((V,E\_L\text{'}),\; s,\; t)$ with contains no $s$–$t$ path. This means that the subgraph resulting from removing all saturated edges (edges $(u,v)$ with $f\text{'}(u,v)=c\_f|\_\{E\_L\}(u,v)$) does not contain any path from $s$ to $t$. In other terms, the blocking flow is such that every possible path from $s$ to $t$ contains a saturated edge.{{sfn|Tarjan|1983|p=102}}

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\backslash in\; E$.
2. Construct $G\_L$ from $G\_f$ of $G$. If $\backslash operatorname\{dist\}(t)\; =\; \backslash infty$, stop and output $f$.
3. Find a blocking flow $f\text{'}$ in $G\_L$.
4. Augment flow $f$ by $f\text{'}$ and go back to step 2.

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 $|V|-1$ blocking flows in the algorithm. For each of them:

• the level graph $G\_L$ can be constructed by breadth-first search in $O(E)$ time
• a blocking flow in the level graph $G\_L$ can be found in $O(VE)$ timeFinding the blocking flow can be implemented in $O(E)$ per path via a sequence of Advance and Retreat operations. See http://courses.csail.mit.edu/6.854/06/scribe/scribe11.pdf for more details.

with total running time $O(E\; +\; VE)\; =\; O(VE)$ for each layer. As a consequence, the running time of Dinic's algorithm is $O(V^2\; E)$.{{cite book | first=Yefim | last=Dinitz | author-link=Yefim Dinitz | editor1=Oded Goldreich | editor-link1=Oded Goldreich | editor2=Arnold L. Rosenberg | editor-link2=Arnold L. Rosenberg | editor3=Alan L. Selman | editor-link3=Alan Selman | title=Theoretical Computer Science: Essays in Memory of Shimon Even | chapter=Dinitz' Algorithm: The Original Version and Even's Version | series=Lecture Notes in Computer Science | year=2006 | volume=3895 | publisher=Springer | isbn=978-3-540-32880-3 | pages=218–240 | doi=10.1007/11685654_10 | chapter-url=https://link.springer.com/chapter/10.1007/11685654_10}}

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

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(\backslash sqrt\{E\})$ and $O(V^\{2/3\})$.The $O(V^\{2/3\})$ bound assumes that no two edges connect the same pair of vertices in the same direction, while the $O(\backslash sqrt\; E)$ bound makes no such assumption. Thus the algorithm runs in $O(\backslash min\backslash \{V^\{2/3\},\; E^\{1/2\}\backslash \}E)$ time.{{cite journal|last1=Even|first1=Shimon|last2=Tarjan|first2=R. Endre|year=1975|title=Network Flow and Testing Graph Connectivity|journal=SIAM Journal on Computing|volume=4|issue=4|pages=507–518|issn=0097-5397|doi=10.1137/0204043}}

In networks that arise from the bipartite matching problem, the number of phases is bounded by $O(\backslash sqrt\{V\})$, therefore leading to the $O(\backslash 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.{{sfn|Tarjan|1983|p=102}}

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

• Ford–Fulkerson algorithm
• Maximum flow problem

{{reflist|group=Note}}

{{Reflist}}

• {{cite book | first=Yefim | last=Dinitz | author-link=Yefim Dinitz | editor1=Oded Goldreich | editor-link1=Oded Goldreich | editor2=Arnold L. Rosenberg | editor-link2=Arnold L. Rosenberg | editor3=Alan L. Selman | editor-link3=Alan Selman | title=Theoretical Computer Science: Essays in Memory of Shimon Even | chapter=Dinitz' Algorithm: The Original Version and Even's Version | series=Lecture Notes in Computer Science | year=2006 | volume=3895 | publisher=Springer | isbn=978-3-540-32880-3 | pages=218–240 | doi=10.1007/11685654_10 | chapter-url=https://link.springer.com/chapter/10.1007/11685654_10}}
• {{cite conference | date=18 April 2019 | place=Ben-Gurion University | first1=Ilan | last1=Kadar | first2=Sivan | last2=Albagli | title=Dinitz's algorithm for finding a maximum flow in a network | no-pp=yes | url=https://slideplayer.com/slide/16480683/ | url-status=live | archive-url=https://web.archive.org/web/20231222225209/https://slideplayer.com/slide/16480683/ | archive-date=22 December 2023}}
• {{cite book | last1=Korte | first1=B. H. | last2=Vygen | first2=Jens | 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}}
• {{cite book | last=Tarjan | first=R. E. |year =1983 | title=Data structures and network algorithms }}

{{Optimization algorithms|combinatorial}}

Category:Network flow problem

Category:Graph algorithms