Алгоритм Диница: Максимальный поток через слоистые сети

Главная инновация алгоритма Диница заключается во введении концепции Слоистой сети (Layered Network) и использовании Блокирующих потоков. Вместо того чтобы жадно искать один единственный увеличивающий путь от Истока к Стоку (как это делает алгоритм Эдмондса-Карпа), алгоритм Диница находит сразу целый набор путей за одну итерацию (фазу).

Алгоритм работает в два этапа на каждой фазе:

1. Построение слоистой сети (с помощью BFS): Алгоритм поиска в ширину проходит по остаточной сети и присваивает каждой вершине "уровень" (кратчайшее расстояние в ребрах от Истока). В слоистую сеть включаются только те ребра, которые ведут строго из уровня k в уровень k+1. Это гарантирует, что мы рассматриваем только кратчайшие пути, и алгоритм не ходит кругами.
2. Поиск блокирующего потока (с помощью DFS): В построенной слоистой сети запускается поиск в глубину. Его задача — пустить максимальный поток так, чтобы каждый путь от Истока к Стоку содержал хотя бы одно полностью насыщенное ребро. Для ускорения DFS используется указатель на текущее ребро: если мы выяснили, что через ребро больше нельзя пустить поток (тупик), мы удаляем его из рассмотрения до конца фазы.

Математический анализ показывает, что после каждого найденного блокирующего потока кратчайшее расстояние от Истока к Стоку в остаточной сети строго увеличивается как минимум на 1. Поскольку максимальная длина пути не может превышать числа вершин V, алгоритм совершит не более V фазов. Построение слоистой сети занимает O(E), а поиск блокирующего потока O(V*E). В итоге общая асимптотическая сложность составляет великолепные O(V^2 * E).

Для специальных сетей (например, для поиска максимального паросочетания в двудольных графах, где пропускная способность всех ребер равна 1) алгоритм Диница работает еще быстрее, достигая времени O(E * sqrt(V)). Позднее эта модификация была независимо переоткрыта и названа Алгоритмом Хопкрофта-Карпа.