Алгоритм Диница

Пусть ${\displaystyle G=((V,E),c,s,t)}$ — транспортная сеть, в которой ${\displaystyle c(u,v)}$ и ${\displaystyle f(u,v)}$ — соответственно пропускная способность и поток через ребро ${\displaystyle (u,v)}$.

Остаточная пропускная способность — отображение ${\displaystyle c_{f}\colon V\times V\to R^{+}}$ определённое как:

1. Если ${\displaystyle (u,v)\in E}$,

   ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$

   ${\displaystyle c_{f}(v,u)=f(u,v)}$

2. ${\displaystyle c_{f}(u,v)=0}$ иначе.

Остаточная сеть — граф ${\displaystyle G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)}$, где

${\displaystyle E_{f}=\{(u,v)\in V\times V\mid c_{f}(u,v)>0\}}$.

Дополняющий путь — ${\displaystyle s-t}$ путь в остаточном графе ${\displaystyle G_{f}}$.

Пусть ${\displaystyle \operatorname {dist} (v)}$ — длина кратчайшего пути из ${\displaystyle s}$ в ${\displaystyle v}$ в графе ${\displaystyle G_{f}}$. Тогда вспомогательная сеть графа ${\displaystyle G_{f}}$ — граф ${\displaystyle G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)}$, где

${\displaystyle E_{L}=\{(u,v)\in E_{f}\mid \operatorname {dist} (v)=\operatorname {dist} (u)+1\}}$.

Блокирующий поток — ${\displaystyle s-t}$ поток ${\displaystyle f}$ такой, что граф ${\displaystyle G'=(V,E_{L}',s,t)}$ с ${\displaystyle E_{L}'=\{(u,v)\mid f(u,v)<c_{f}|_{E_{L}}(u,v)\}}$ не содержит ${\displaystyle s-t}$ пути.

Алгоритм Диница

Вход: Сеть ${\displaystyle G=((V,E),c,s,t)}$.

Выход: ${\displaystyle s-t}$ поток ${\displaystyle f}$ максимальной величины.

1. Установить ${\displaystyle f(e)=0}$ для каждого ${\displaystyle e\in E}$.
2. Создать ${\displaystyle G_{L}}$ из ${\displaystyle G_{f}}$ графа ${\displaystyle G}$. Если ${\displaystyle \operatorname {dist} (t)=\infty }$, остановиться и вывести ${\displaystyle f}$.
3. Найти блокирующий поток ${\displaystyle f\;'}$ в ${\displaystyle G_{L}}$.
4. Дополнить поток ${\displaystyle \ f}$ потоком ${\displaystyle f\;'}$ и перейти к шагу 2.

Можно показать, что каждый раз число рёбер кратчайшем пути из источника в сток увеличивается хотя бы на единицу, поэтому в алгоритме не более ${\displaystyle n-1}$ блокирующих потоков, где ${\displaystyle n}$ — число вершин в сети. Вспомогательная сеть ${\displaystyle G_{L}}$ может быть построена обходом в ширину за время ${\displaystyle O(E)}$, а блокирующий поток на каждом уровне графа может быть найден за время ${\displaystyle O(VE)}$. Поэтому время работы алгоритма Диница есть ${\displaystyle O(V)\cdot (O(E)+O(VE))=O(V^{2}E)}$.

Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время ${\displaystyle O(E\log V)}$, тогда время работы алгоритма Диница может быть улучшено до ${\displaystyle O(VE\log V)}$.

Ниже приведена симуляция алгоритма Диница. Во вспомогательной сети ${\displaystyle G_{L}}$ вершины с красными метками — значения ${\displaystyle \operatorname {dist} (v)}$. Блокирующий поток помечен синим.

	${\displaystyle G}$	${\displaystyle G_{f}}$	${\displaystyle G_{L}}$
1.
	Блокирующий поток состоит из путей: ${\displaystyle \{s,1,3,t\}}$ с 4 единицами потока, ${\displaystyle \{s,1,4,t\}}$ с 6 единицами потока, и ${\displaystyle \{s,2,4,t\}}$ с 4 единицами потока. Следовательно, блокирующий поток содержит 14 единиц, а величина потока ${\displaystyle |f|}$ равна 14. Заметим, что дополняющий путь имеет 3 ребра.
2.
	Блокирующий поток состоит из путей: ${\displaystyle \{s,2,4,3,t\}}$ с 5 единицами потока. Следовательно, блокирующий поток содержит 5 единиц, а величина потока ${\displaystyle |f|}$ равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра.
3.
	Сток ${\displaystyle t}$ не достижим в сети ${\displaystyle G_{f}}$. Поэтому алгоритм останавливается и возвращает максимальный поток величины 19. Заметим, что в каждом блокирующем потоке количество рёбер в дополняющем пути увеличивается хотя бы на одно.

Алгоритм Диница был опубликован в 1970 г. бывшим советским учёным Ефимом Диницем, который сейчас является членом факультета вычислительной техники университета Бен-Гурион (Израиль), ранее, чем алгоритм Эдмондса — Карпа, который был опубликован в 1972, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.

• Yefim Dinitz. Dinitz' Algorithm: The Original Version and Even's Version // Theoretical Computer Science: Essays in Memory of Shimon Even (англ.) / Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman. — Springer, 2006. — P. 218—240. — ISBN 978-3540328803.
• B. H. Korte, Jens Vygen. 8.4 Blocking Flows and Fujishige's Algorithm // Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21) (англ.). — Springer Berlin Heidelberg, 2008. — P. 174—176. — ISBN 978-3-540-71844-4.

• Алгоритм Диница на сайте e-maxx.ru: Описание, доказательства, реализация на C++