Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети, предложенный в 1970 году советским (впоследствии израильским) математиком Ефимом Диницем[англ.]. Временная сложность алгоритма составляет
. Получить такую оценку позволяет введение понятий вспомогательной сети и блокирующего (псевдомаксимального) потока. В сетях с единичными пропускными способностями существует более сильная оценка временной сложности:
.
Пусть
— транспортная сеть, в которой
и
— соответственно пропускная способность и поток через ребро
.
- Остаточная пропускная способность — отображение
определённое как:
- Если
,
![{\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2756fd42d49a52b35b33bfe377a74dcbdf1f4b5)
В других источниках ![{\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3f47527630bf5f371443382c9014a044cd687df)
иначе.
- Остаточная сеть — граф
, где
.
- Дополняющий путь —
путь в остаточном графе
.
- Пусть
— длина кратчайшего пути из
в
в графе
. Тогда вспомогательная сеть графа
— граф
, где
.
- Блокирующий поток —
поток
такой, что граф
с
не содержит
пути.
Алгоритм Диница
- Вход: Сеть
.
- Выход:
поток
максимальной величины.
- Установить
для каждого
.
- Создать
из
графа
. Если
, остановиться и вывести
.
- Найти блокирующий поток
в
.
- Дополнить поток
потоком
и перейти к шагу 2.
Можно показать, что каждый раз число в рёбер кратчайшем пути из источника в сток увеличивается хотя бы на единицу, поэтому в алгоритме не более
блокирующих потоков, где
— число вершин в сети. Вспомогательная сеть
может быть построена обходом в ширину за время
, а блокирующий поток на каждом уровне графа может быть найден за время
. Поэтому время работы алгоритма Диница есть
.
Используя структуры данных, называемые динамические деревья, можно находить блокирующий поток на каждой фазе за время
, тогда время работы алгоритма Диница может быть улучшено до
.
Ниже приведена симуляция алгоритма Диница. Во вспомогательной сети
вершины с красными метками — значения
. Блокирующий поток помечен синим.
|
|
|
|
1.
|
|
|
|
|
Блокирующий поток состоит из путей:
с 4 единицами потока,
с 6 единицами потока, и
с 4 единицами потока.
Следовательно, блокирующий поток содержит 14 единиц, а величина потока равна 14. Заметим, что дополняющий путь имеет 3 ребра.
|
2.
|
|
|
|
|
Блокирующий поток состоит из путей:
с 5 единицами потока.
Следовательно, блокирующий поток содержит 5 единиц, а величина потока равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра.
|
3.
|
|
|
|
|
Сток не достижим в сети . Поэтому алгоритм останавливается и возвращает максимальный поток величины 19. Заметим, что в каждом блокирующем потоке количество рёбер в дополняющем пути увеличивается хотя бы на одно.
|
Алгоритм Диница был опубликован в 1970 г. бывшим советским учёным Ефимом Диницем, который сейчас является членом факультета вычислительной техники университета Бен-Гурион (Израиль), ранее, чем алгоритм Эдмондса — Карпа, который был опубликован в 1972, но создан ранее. Они независимо показали, что в алгоритме Форда — Фалкерсона в случае, если дополняющий путь является кратчайшим, длина дополняющего пути не уменьшается.
Временную сложность алгоритма можно уменьшить, если оптимизировать процесс поиска блокирующего потока. Для этого необходимо ввести понятие потенциала. Потенциал ребра
есть
, а потенциал вершины
равен
. По той же логике
, а
. Идея улучшения заключается в том, чтобы искать вершину с минимальным положительным потенциалом в вспомогательной сети и строить блокирующий поток через нее, используя очереди.
- Вход: Сеть
.
- Выход:
поток
максимальной величины.
- Установить
для каждого
.
- Создать
из
графа
. Если
, остановиться и вывести
.
- Установить
для каждого
.
- Определить потенциал каждой вершины.
- Пока существует вершина
такая, что
:
- Определи поток
при помощи прямого распостранения из
.
- Определи поток
при помощи обратного распостранения из
.
- Дополни поток
потоками
и
.
- Дополнить поток
потоком
и перейти к шагу 2.
Алгоритмы прямого и обратного распостранения служат поиску путей из
в
и из
в
соответственно. Пример работы алгоритма прямого распостранения с использованием очередей:
- Вход: Вспомогательная сеть
, вершина
такая, что
.
- Выход: Поток
из источника
в вершину
, являющийся частью блокирующего потока.
- Установить для всех
:
.
- Установить
и
.
- Добавить
в очередь
.
- Пока очередь
не пуста:
- Установить значение
равным последнему элементу очереди.
- Пока
:
- Для каждого ребра
:
.
- Обнови
.
- Обнови
.
- Установи
.
- Если
и
удалить
из очереди
.
В связи с тем, что в каждой итерации поиска блокирующего потока «насыщается» минимум одна вершина, он завершается за
итераций в худшем случае, в каждой из которых рассматриваются максимум
вершин. Пусть
— количество «насыщенных» ребер в каждой
-той итерации поиска блокирующего потока. Тогда его асимптотическая сложность равна
, где
— количество вершин и
— количество ребер в графе. Таким образом, асимптотическая сложность алгоритма Диница с распостранением равна
, так как блокирующий поток может проходить максимум через
вершин.