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