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

Перейти к навигацииПерейти к поиску

Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком Ефимом Диницем[англ.]. Временная сложность алгоритма составляет . Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности: .

Описание

Пусть  — транспортная сеть, в которой и  — соответственно пропускная способность и поток через ребро .

Остаточная пропускная способность — отображение определённое как:
  1. Если ,
    В других источниках
  2. иначе.
Остаточная сеть — граф , где
.
Дополняющий путь — путь в остаточном графе .
Пусть  — длина кратчайшего пути из в в графе . Тогда вспомогательная сеть графа  — граф , где
.
Блокирующий поток — поток такой, что граф с не содержит пути.

Алгоритм

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

Вход: Сеть .
Выход: поток максимальной величины.
  1. Установить для каждого .
  2. Создать из графа . Если , остановиться и вывести .
  3. Найти блокирующий поток в .
  4. Дополнить поток потоком и перейти к шагу 2.

Анализ

Можно показать, что каждый раз число в рёбер кратчайшем пути из источника в сток увеличивается хотя бы на единицу, поэтому в алгоритме не более блокирующих потоков, где  — число вершин в сети. Вспомогательная сеть может быть построена обходом в ширину за время , а блокирующий поток на каждом уровне графа может быть найден за время . Поэтому время работы алгоритма Диница есть .

Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время , тогда время работы алгоритма Диница может быть улучшено до .

Пример

Ниже приведена симуляция алгоритма Диница. Во вспомогательной сети вершины с красными метками — значения . Блокирующий поток помечен синим.

1.

Блокирующий поток состоит из путей:

  1. с 4 единицами потока,
  2. с 6 единицами потока, и
  3. с 4 единицами потока.

Следовательно, блокирующий поток содержит 14 единиц, а величина потока равна 14. Заметим, что дополняющий путь имеет 3 ребра.

2.

Блокирующий поток состоит из путей:

  1. с 5 единицами потока.

Следовательно, блокирующий поток содержит 5 единиц, а величина потока равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра.

3.

Сток не достижим в сети . Поэтому алгоритм останавливается и возвращает максимальный поток величины 19. Заметим, что в каждом блокирующем потоке количество рёбер в дополняющем пути увеличивается хотя бы на одно.

История

Алгоритм Диница был опубликован в 1970 г. бывшим советским учёным Ефимом Диницем, который сейчас является членом факультета вычислительной техники университета Бен-Гурион (Израиль), ранее, чем алгоритм Эдмондса — Карпа, который был опубликован в 1972, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.

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

Временную сложность алгоритма можно уменьшить, если оптимизировать процесс поиска блокирующего потока. Для этого необходимо ввести понятие потенциала. Потенциал ребра есть , а потенциал вершины равен . По той же логике , а . Идея улучшения заключается в том, чтобы искать вершину с минимальным положительным потенциалом в вспомогательной сети и строить блокирующий поток через нее, используя очереди.

Вход: Сеть .
Выход: поток максимальной величины.
  1. Установить для каждого .
  2. Создать из графа . Если , остановиться и вывести .
  3. Установить для каждого .
  4. Определить потенциал каждой вершины.
  5. Пока существует вершина такая, что :
    1. Определи поток при помощи прямого распространения из .
    2. Определи поток при помощи обратного распространения из .
    3. Дополни поток потоками и .
  6. Дополнить поток потоком и перейти к шагу 2.

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

Вход: Вспомогательная сеть , вершина такая, что .
Выход: Поток из источника в вершину , являющийся частью блокирующего потока.
  1. Установить для всех : .
  2. Установить и .
  3. Добавить в очередь .
  4. Пока очередь не пуста:
    1. Установить значение равным последнему элементу очереди.
    2. Пока :
      1. Для каждого ребра :
      2. .
      3. Обнови .
      4. Обнови .
      5. Установи .
      6. Если и удалить из очереди .

В связи с тем, что в каждой итерации поиска блокирующего потока «насыщается» минимум одна вершина, он завершается за итераций в худшем случае, в каждой из которых рассматриваются максимум вершин. Пусть  — количество «насыщенных» ребер в каждой -той итерации поиска блокирующего потока. Тогда его асимптотическая сложность равна , где  — количество вершин и  — количество ребер в графе. Таким образом, асимптотическая сложность алгоритма Диница с распространением равна , так как блокирующий поток может проходить максимум через вершин.

Литература

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

Ссылки