---
title: Dinic's algorithm
slug: dinic-s-algorithm
qid: 
snapshot: enwiki-001374875607
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1374875607
tags: [23221441, 23603337, 26220375, 29176510]
---

# Dinic's algorithm

> [!note] Provenance
> Snapshot `enwiki-001374875607` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1374875607> · Licensed CC BY-SA 4.0

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

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 Dinitz. The algorithm runs in O(|V|^2|E|) time and is similar to the Edmonds–Karp algorithm, which runs in O(|V||E|^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. ==History== 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: 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. ==Definition== 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\colon V\times V \to R^+ defined as, if (u,v)\in E , c_f(u,v) = c(u,v) - f(u,v) if (v,u)\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 = \{(u,v)\in V \times V \colon\; 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 \colon\; \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) \colon\; f'(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 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) time 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) . 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) . ==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 \operatorname{dist}(v) . The paths in blue form a blocking flow. ==See also== Ford–Fulkerson algorithm Maximum flow problem ==References==
