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

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

Описание

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

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

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

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

   $c_{f}(v,u)=f(u,v)$ В других источниках $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$

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}',c_{f}|_{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(|V|+|E|)$, а блокирующий поток на каждом уровне графа может быть найден за время $O(|V||E|)$. Поэтому время работы алгоритма Диница есть $O(|V|)\cdot (O(|V|+|E|)+O(|V||E|))=O(|V|^{2}|E|)$.

Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время $O(|E|\log |V|)$, тогда время работы алгоритма Диница может быть улучшено до $O(|V||E|\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, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.

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

Временную сложность алгоритма можно уменьшить, если оптимизировать процесс поиска блокирующего потока. Для этого необходимо ввести понятие потенциала. Потенциал ребра $e\in E$ есть $\operatorname {pot} (e)=c_{f}(e)$, а потенциал вершины $v\in V\setminus \{s,t\}$ равен $\operatorname {pot} (v)=\min\{\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e),\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)\}$. По той же логике $\operatorname {pot} (s)=\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e)$, а $\operatorname {pot} (t)=\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)$ . Идея улучшения заключается в том, чтобы искать вершину с минимальным положительным потенциалом в вспомогательной сети и строить блокирующий поток через нее, используя очереди.

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

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

1. Установить $f(e)=0$ для каждого $e\in E$.
2. Создать $G_{L}$ из $G_{f}$ графа $G$. Если $\operatorname {dist} (s,t)=\infty$, остановиться и вывести $f$.
3. Установить $f'(e)=0$ для каждого $e\in E$.
4. Определить потенциал каждой вершины.
5. Пока существует вершина $v\in V$ такая, что $\operatorname {pot} (v)>0$:
   1. Определи поток $f''$ при помощи прямого распространения из $v$.
   2. Определи поток $f'''$ при помощи обратного распространения из $v$.
   3. Дополни поток $f'$ потоками $f''$ и $f'''$.
6. Дополнить поток $f$ потоком $f'$ и перейти к шагу 2.

Алгоритмы прямого и обратного распространения служат поиску путей из $v$ в $t$ и из $s$ в $v$ соответственно. Пример работы алгоритма прямого распространения с использованием очередей:

Вход: Вспомогательная сеть $G_{L}=(V,E_{L},c_{f}|_{E_{L}},s,t)$, вершина $v\in V$ такая, что $\operatorname {pot} (v)>0$.

Выход: Поток $f''$ из источника $s$ в вершину $v$, являющийся частью блокирующего потока.

1. Установить для всех $w\in V\setminus \{v\}$: $U(w)=0$.
2. Установить $U(v)=\operatorname {pot} (v)$ и $\operatorname {pot} (v)=0$.
3. Добавить $v$ в очередь $Q$.
4. Пока очередь $Q$ не пуста:
   1. Установить значение $v$ равным последнему элементу очереди.
   2. Пока $U(v)>0$:
      1. Для каждого ребра $e=(v,w)\in \delta ^{+}(v)$:
      2. $f''(e)=\min\{\operatorname {pot} (e),U(v)\}$.
      3. Обнови $U(v)=U(v)-f''(e)$.
      4. Обнови $U(w)=U(w)+f''(e)$.
      5. Установи $\operatorname {pot} (w)=\operatorname {pot} (w)-\operatorname {pot} (e)$.
      6. Если $w\neq t$ и $U(w)=f''(e)$ удалить $w$ из очереди $Q$.

В связи с тем, что в каждой итерации поиска блокирующего потока «насыщается» минимум одна вершина, он завершается за $|V|-1$ итераций в худшем случае, в каждой из которых рассматриваются максимум $|V|$ вершин. Пусть $l_{i}$ — количество «насыщенных» ребер в каждой $i$-той итерации поиска блокирующего потока. Тогда его асимптотическая сложность равна $\sum _{i=1}^{n-1}O(n+l_{i})=O(n^{2}+\sum _{i=1}^{n-1}l_{i})=O(n^{2}+m)$, где $n$ — количество вершин и $m$ — количество ребер в графе. Таким образом, асимптотическая сложность алгоритма Диница с распространением равна $O(|V|^{3})$, так как блокирующий поток может проходить максимум через $|V|$ вершин.

Литература

• 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++