Русская Википедия:Алгоритм Диница
Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком Ефимом Диницем. Временная сложность алгоритма составляет <math>O(|V|^2|E|)</math>. Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: <math>O(|E||V|)</math>.
Описание
Пусть <math>G = (V,E,c,s,t)</math> — транспортная сеть, в которой <math>c(u,v)</math> и <math>f(u,v)</math> — соответственно пропускная способность и поток через ребро <math>(u,v)</math>.
- Остаточная пропускная способность — отображение <math>c_f\colon V\times V \to \mathbb{R}^+</math> определённое как:
- Если <math>(u,v)\in E</math>,
- <math>c_f(u,v) = c(u,v) - f(u,v) </math>
- <math>c_f(v,u) = f(u,v)</math> В других источниках <math>c_f(u, v) = c(u, v) - f(u, v) + f(v, u)</math>
- <math>c_f(u,v) = 0</math> иначе.
- Если <math>(u,v)\in E</math>,
- Остаточная сеть — граф <math>G_f = (V, E_f, c_f|_{E_f}, s, t)</math>, где
- <math>E_f = \{(u,v)\in V \times V \mid c_f(u,v) > 0\}</math>.
- Дополняющий путь — <math>s-t</math> путь в остаточном графе <math>G_f</math>.
- Пусть <math>\operatorname{dist}(v)</math> — длина кратчайшего пути из <math>s</math> в <math>v</math> в графе <math>G_f</math>. Тогда вспомогательная сеть графа <math>G_f</math> — граф <math>G_L = (V, E_L, c_f|_{E_L}, s,t)</math>, где
- <math>E_L = \{(u,v)\in E_f \mid \operatorname{dist}(v) = \operatorname{dist}(u) + 1\}</math>.
- Блокирующий поток — <math>s-t</math> поток <math>f</math> такой, что граф <math>G' = (V,E_L',c_f|_{E_L}, s, t)</math> с <math>E_L' = \{(u,v) \mid f(u,v) < c_f|_{E_L}(u,v)\}</math> не содержит <math>s-t</math> пути.
Алгоритм
Алгоритм Диница
- Вход: Сеть <math>G = (V, E, c, s, t)</math>.
- Выход: <math>s-t</math> поток <math>f</math> максимальной величины.
- Установить <math>f(e) = 0</math> для каждого <math>e\in E</math>.
- Создать <math>G_L</math> из <math>G_f</math> графа <math>G</math>. Если <math>\operatorname{dist}(t) = \infty</math>, остановиться и вывести <math>f</math>.
- Найти блокирующий поток <math>f'</math> в <math>G_L</math>.
- Дополнить поток <math>f</math> потоком <math>f'</math> и перейти к шагу 2.
Анализ
Можно показать, что каждый раз число в рёбер кратчайшем пути из источника в сток увеличивается хотя бы на единицу, поэтому в алгоритме не более <math>n-1</math> блокирующих потоков, где <math>n</math> — число вершин в сети. Вспомогательная сеть <math>G_L</math> может быть построена обходом в ширину за время <math>O(|V| + |E|)</math>, а блокирующий поток на каждом уровне графа может быть найден за время <math>O(|V||E|)</math>. Поэтому время работы алгоритма Диница есть <math>O(|V|) \cdot (O(|V|+|E|) + O(|V||E|)) = O(|V|^2 |E|)</math>.
Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время <math>O(|E| \log |V|)</math>, тогда время работы алгоритма Диница может быть улучшено до <math>O(|V||E| \log |V|)</math>.
Пример
Ниже приведена симуляция алгоритма Диница. Во вспомогательной сети <math>G_L</math> вершины с красными метками — значения <math>\operatorname{dist}(v)</math>. Блокирующий поток помечен синим.
| <math>G</math> | <math>G_f</math> | <math>G_L</math> | |
|---|---|---|---|
| 1. | Файл:Dinic algorithm G1.svg | Файл:Dinic algorithm Gf1.svg | Файл:Dinic algorithm GL1.svg |
|
Блокирующий поток состоит из путей:
Следовательно, блокирующий поток содержит 14 единиц, а величина потока <math>|f|</math> равна 14. Заметим, что дополняющий путь имеет 3 ребра. | |||
| 2. | Файл:Dinic algorithm G2.svg | Файл:Dinic algorithm Gf2.svg | Файл:Dinic algorithm GL2.svg |
|
Блокирующий поток состоит из путей:
Следовательно, блокирующий поток содержит 5 единиц, а величина потока <math>|f|</math> равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра. | |||
| 3. | Файл:Dinic algorithm G3.svg | Файл:Dinic algorithm Gf3.svg | Файл:Dinic algorithm GL3.svg |
|
Сток <math>t</math> не достижим в сети <math>G_f</math>. Поэтому алгоритм останавливается и возвращает максимальный поток величины 19. Заметим, что в каждом блокирующем потоке количество рёбер в дополняющем пути увеличивается хотя бы на одно. | |||
История
Алгоритм Диница был опубликован в 1970 г. бывшим советским учёным Ефимом Диницем, который сейчас является членом факультета вычислительной техники университета Бен-Гурион (Израиль), ранее, чем алгоритм Эдмондса — Карпа, который был опубликован в 1972, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.
Алгоритм Диница с распостранением
Временную сложность алгоритма можно уменьшить, если оптимизировать процесс поиска блокирующего потока. Для этого необходимо ввести понятие потенциала. Потенциал ребра <math>e \in E</math> есть <math>\operatorname{pot}(e) = c_f(e)</math>, а потенциал вершины <math>v \in V \setminus \{s, t\}</math> равен <math>\operatorname{pot}(v) = \min\{ \sum_{e \in \delta^+(v)} \operatorname{pot}(e), \sum_{e \in \delta^-(v)} \operatorname{pot}(e) \}</math>. По той же логике <math>\operatorname{pot}(s) = \sum_{e \in \delta^+(v)} \operatorname{pot}(e)</math>, а <math>\operatorname{pot}(t) = \sum_{e \in \delta^-(v)} \operatorname{pot}(e)</math> . Идея улучшения заключается в том, чтобы искать вершину с минимальным положительным потенциалом в вспомогательной сети и строить блокирующий поток через нее, используя очереди.
- Вход: Сеть <math>G = (V, E, c, s, t)</math>.
- Выход: <math>s-t</math> поток <math>f</math> максимальной величины.
- Установить <math>f(e) = 0</math> для каждого <math>e\in E</math>.
- Создать <math>G_L</math> из <math>G_f</math> графа <math>G</math>. Если <math>\operatorname{dist}(s, t) = \infty</math>, остановиться и вывести <math>f</math>.
- Установить <math>f'(e) = 0</math> для каждого <math>e\in E</math>.
- Определить потенциал каждой вершины.
- Пока существует вершина <math>v \in V</math> такая, что <math>\operatorname{pot}(v) > 0</math>:
- Определи поток <math>f</math> при помощи прямого распостранения из <math>v</math>.
- Определи поток <math>f</math> при помощи обратного распостранения из <math>v</math>.
- Дополни поток <math>f'</math> потоками <math>f</math> и <math>f'</math>.
- Дополнить поток <math>f</math> потоком <math>f'</math> и перейти к шагу 2.
Алгоритмы прямого и обратного распостранения служат поиску путей из <math>v</math> в <math>t</math> и из <math>s</math> в <math>v</math> соответственно. Пример работы алгоритма прямого распостранения с использованием очередей:
- Вход: Вспомогательная сеть <math>G_L = (V, E_L, c_f|_{E_L}, s,t)</math>, вершина <math>v \in V</math> такая, что <math>\operatorname{pot}(v) > 0</math>.
- Выход: Поток <math>f</math> из источника <math>s</math> в вершину <math>v</math>, являющийся частью блокирующего потока.
- Установить для всех <math>w \in V \setminus \{v\}</math>: <math>U(w) = 0</math>.
- Установить <math>U(v) = \operatorname{pot}(v)</math> и <math>\operatorname{pot}(v) = 0</math>.
- Добавить <math>v</math> в очередь <math>Q</math>.
- Пока очередь <math>Q</math> не пуста:
- Установить значение <math>v</math> равным последнему элементу очереди.
- Пока <math>U(v) > 0</math>:
- Для каждого ребра <math>e = (v, w) \in \delta^+ (v)</math>:
- <math>f(e) = \min\{ \operatorname{pot}(e), U(v) \}</math>.
- Обнови <math>U(v) = U(v) - f(e)</math>.
- Обнови <math>U(w) = U(w) + f(e)</math>.
- Установи <math>\operatorname{pot}(w) = \operatorname{pot}(w) - \operatorname{pot}(e)</math>.
- Если <math>w \neq t</math> и <math>U(w) = f(e)</math> удалить <math>w</math> из очереди <math>Q</math>.
В связи с тем, что в каждой итерации поиска блокирующего потока "насыщается" минимум одна вершина, он завершается за <math>|V| - 1</math> итераций в худшем случае, в каждой из которых рассматриваются максимум <math>|V|</math> вершин. Пусть <math>l_i</math> - количество "насыщенных" ребер в каждой <math>i</math>-той итерации поиска блокирующего потока. Тогда его асимптотическая сложность равна <math>\sum_{i=1}^{n-1} O(n + l_i) = O(n^2 + \sum_{i=1}^{n-1} l_i) = O(n^2 + m)</math>, где <math>n</math> - количество вершин и <math>m</math> - количество ребер в графе. Таким образом, асимптотическая сложность алгоритма Диница с распостранением равна <math>O(|V|^3)</math>, так как блокирующий поток может проходить максимум через <math>|V|</math> вершин.
Литература
Ссылки
