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