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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Описание[править | править код]

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

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

Алгоритм[править | править код]

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

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

Анализ[править | править код]

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

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

Пример[править | править код]

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

1. Dinic algorithm G1.svg Dinic algorithm Gf1.svg Dinic algorithm GL1.svg

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

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

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

2. Dinic algorithm G2.svg Dinic algorithm Gf2.svg Dinic algorithm GL2.svg

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

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

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

3. Dinic algorithm G3.svg Dinic algorithm Gf3.svg Dinic algorithm GL3.svg

Сток не достижим в сети . Поэтому алгоритм останавливается и возвращает максимальный поток величины 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. Если и удалить из очереди .

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

Литература[править | править код]

Ссылки[править | править код]