Алгоритм Диница
Данный алгоритм использует ту же идею, что и алгоритм Эдмондса-Карпа, мы будет пускать поток только вдоль кратчайших путей.
Определение:
Слоистая сеть —это сеть состоящая только из таких рёбер $(v, u)$ сети $G$, что $d(v) + 1 = d(u)$, где $d$ - расстояние от истока.
Схема алгоритма:
- Посторить слоистую сеть по остаточной, если сток не достижим то завершить алгоритм
- Пустить блокирующий поток в слоистой сети
Если алгоритм завершился, то в остаточной сети сток не достижим из истока, а значит не существует увеличиваещего пути, следовательно найденый поток максимален.
Утверждение:
После каждой итерации алгоритма расстояние до стока строго увеличивается
Доказательство данного факта тривиально
Так как расстояние строго увеличивается количество итераций алгоритма = $O(V)$. В зависимости от выбора алгоритма поиска блокирующего потока время данного алгоритма может составить $O(VE^2)$, $O(V^2E)$ или $O(V^3)$.