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

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

Описание

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

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

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$.

Пусть $\mathrm{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 \mathrm{dist}(v)=\mathrm{dist}(u)+1\}$.

Блокирующий поток — $s-t$ поток $f$ такой, что граф $G^{\prime }=(V,{E_L}^{\prime },c_f{|}_{E_L},s,t)$ с ${E_L}^{\prime }=\{(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$. Если $\mathrm{dist}(t)=\mathrm{\infty }$, остановиться и вывести $f$.
3. Найти блокирующий поток $f^{\prime }$ в $G_L$.
4. Дополнить поток $f$ потоком $f^{\prime }$ и перейти к шагу 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$ вершины с красными метками — значения $\mathrm{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$ есть $\mathrm{pot}(e)=c_f(e)$, а потенциал вершины $v\in V\setminus \{s,t\}$ равен $\mathrm{pot}(v)=min\{\sum _{e\in {\delta }^{+}(v)}\mathrm{pot}(e),\sum _{e\in {\delta }^{-}(v)}\mathrm{pot}(e)\}$. По той же логике $\mathrm{pot}(s)=\sum _{e\in {\delta }^{+}(v)}\mathrm{pot}(e)$, а $\mathrm{pot}(t)=\sum _{e\in {\delta }^{-}(v)}\mathrm{pot}(e)$ . Идея улучшения заключается в том, чтобы искать вершину с минимальным положительным потенциалом в вспомогательной сети и строить блокирующий поток через нее, используя очереди.

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

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

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

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

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

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

1. Установить для всех $w\in V\setminus \{v\}$: $U(w)=0$.
2. Установить $U(v)=\mathrm{pot}(v)$ и $\mathrm{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\{\mathrm{pot}(e),U(v)\}$.
      3. Обнови $U(v)=U(v)-f^{″}(e)$.
      4. Обнови $U(w)=U(w)+f^{″}(e)$.
      5. Установи $\mathrm{pot}(w)=\mathrm{pot}(w)-\mathrm{pot}(e)$.
      6. Если $w\ne 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|$ вершин.

Литература

• Шаблон:Книга
• Шаблон:Книга

Ссылки

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