Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком . Временная сложность алгоритма составляет . Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: .
Описание Пусть — транспортная сеть, в которой и — соответственно пропускная способность и поток через ребро . Остаточная пропускная способность — отображение определённое как: Если ,
В других источниках иначе.
Остаточная сеть — граф , где .
Дополняющий путь — путь в остаточном графе .
Пусть — длина кратчайшего пути из в в графе . Тогда вспомогательная сеть графа — граф , где .
Блокирующий поток — поток такой, что граф с не содержит пути.
Алгоритм Алгоритм Диница Вход: Сеть . Выход: поток максимальной величины. Установить для каждого . Создать из графа . Если , остановиться и вывести . Найти блокирующий поток в . Дополнить поток потоком и перейти к шагу 2.
Анализ Можно показать, что каждый раз число рёбер в кратчайшем пути из источника в сток увеличивается хотя бы на единицу, поэтому в алгоритме не более блокирующих потоков, где — число вершин в сети. Вспомогательная сеть может быть построена обходом в ширину за время , а блокирующий поток на каждом уровне графа может быть найден за время . Поэтому время работы алгоритма Диница есть .
Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время , тогда время работы алгоритма Диница может быть улучшено до .
Пример Ниже приведена симуляция алгоритма Диница. Во вспомогательной сети вершины с красными метками — значения . Блокирующий поток помечен синим.
1. Блокирующий поток состоит из путей: с 4 единицами потока, с 6 единицами потока, и с 4 единицами потока. Следовательно, блокирующий поток содержит 14 единиц, а величина потока равна 14. Заметим, что дополняющий путь имеет 3 ребра. 2. Блокирующий поток состоит из путей: с 5 единицами потока. Следовательно, блокирующий поток содержит 5 единиц, а величина потока равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра. 3. Сток не достижим в сети . Поэтому алгоритм останавливается и возвращает максимальный поток величины 19. Заметим, что в каждом блокирующем потоке количество рёбер в дополняющем пути увеличивается хотя бы на одно.
История Алгоритм Диница был опубликован в 1970 г. бывшим советским учёным Ефимом Диницем, который сейчас является членом факультета вычислительной техники университета Бен-Гурион (Израиль), ранее, чем алгоритм Эдмондса — Карпа, который был опубликован в 1972, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.
Алгоритм Диница с распространением Временную сложность алгоритма можно уменьшить, если оптимизировать процесс поиска блокирующего потока. Для этого необходимо ввести понятие потенциала. Потенциал ребра есть , а потенциал вершины равен . По той же логике , а . Идея улучшения заключается в том, чтобы искать вершину с минимальным положительным потенциалом в вспомогательной сети и строить блокирующий поток через нее, используя очереди. Вход: Сеть . Выход: поток максимальной величины. Установить для каждого . Создать из графа . Если , остановиться и вывести . Установить для каждого . Определить потенциал каждой вершины. Пока существует вершина такая, что : Определи поток при помощи прямого распространения из . Определи поток при помощи обратного распространения из . Дополни поток потоками и . Дополнить поток потоком и перейти к шагу 2. Алгоритмы прямого и обратного распространения служат поиску путей из в и из в соответственно. Пример работы алгоритма прямого распространения с использованием очередей: Вход: Вспомогательная сеть , вершина такая, что . Выход: Поток из источника в вершину , являющийся частью блокирующего потока. Установить для всех : . Установить и . Добавить в очередь . Пока очередь не пуста: Установить значение равным последнему элементу очереди. Пока : Для каждого ребра : . Обнови . Обнови . Установи . Если и удалить из очереди . В связи с тем, что в каждой итерации поиска блокирующего потока «насыщается» минимум одна вершина, он завершается за итераций в худшем случае, в каждой из которых рассматриваются максимум вершин. Пусть — количество «насыщенных» ребер в каждой -той итерации поиска блокирующего потока. Тогда его асимптотическая сложность равна , где — количество вершин и — количество ребер в графе. Таким образом, асимптотическая сложность алгоритма Диница с распространением равна , так как блокирующий поток может проходить максимум через вершин.
Литература
Ссылки Алгоритм Диница на сайте e-maxx.ru: Описание, доказательства, реализация на C++
Категория:Алгоритмы на графах