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

Описание

Пусть ${\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 \mathbb {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)}$ В других источниках ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)}$

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

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

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

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

Вход : Сеть ${\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} (s,t)=\infty }$ , остановиться и вывести ${\displaystyle f}$ .
3. Установить ${\displaystyle f'(e)=0}$ для каждого ${\displaystyle e\in E}$ .
4. Определить потенциал каждой вершины.
5. Пока существует вершина ${\displaystyle v\in V}$ такая, что ${\displaystyle \operatorname {pot} (v)>0}$ :
   1. Определи поток ${\displaystyle f''}$ при помощи прямого распостранения из ${\displaystyle v}$ .
   2. Определи поток ${\displaystyle f'''}$ при помощи обратного распостранения из ${\displaystyle v}$ .
   3. Дополни поток ${\displaystyle f'}$ потоками ${\displaystyle f''}$ и ${\displaystyle f'''}$ .
6. Дополнить поток ${\displaystyle f}$ потоком ${\displaystyle f'}$ и перейти к шагу 2.

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

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

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

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

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

Литература

• Yefim Dinitz. Dinitz' Algorithm: The Original Version and Even's Version // (англ.) ( (англ.) / (англ.) ( , 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 // (англ.) . — Springer Berlin Heidelberg , 2008. — P. —176. — ISBN 978-3-540-71844-4 .

Ссылки