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

Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком Ефимом Диницем. Временная сложность алгоритма составляет $O(V^{2}E)$. Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: $O(EV)$.

Описание

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

Анализ

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

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

Пример

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

	$G$	$G_{f}$	$G_{L}$
1.
	Блокирующий поток состоит из путей: $\{s,1,3,t\}$ с 4 единицами потока, $\{s,1,4,t\}$ с 6 единицами потока, и $\{s,2,4,t\}$ с 4 единицами потока. Следовательно, блокирующий поток содержит 14 единиц, а величина потока $|f|$ равна 14. Заметим, что дополняющий путь имеет 3 ребра.
2.
	Блокирующий поток состоит из путей: $\{s,2,4,3,t\}$ с 5 единицами потока. Следовательно, блокирующий поток содержит 5 единиц, а величина потока $|f|$ равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра.
3.
	Сток $t$ не достижим в сети $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++