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

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

Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 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, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]