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

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

Описание

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

Остаточная пропускная способность — отображение $c_f : 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 : 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 : \operatorname{dist}(v) = \operatorname{dist}(u) + 1\}$.

Блокирующий поток — $s-t$ поток $f$ такой, что граф $G' = (V,E_L', s, t)$ с $E_L' = \{(u,v) : 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^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++