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

Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком Ефимом Диницем^{<span title="Статья «Диниц, Ефим Абрамович» в русском разделе отсутствует">ru</span>}_en. Временная сложность алгоритма составляет ${\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 // 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++

Эта страница в последний раз была отредактирована 29 марта 2024 в 16:40.