Алгоритм Диница: различия между версиями

Версия 22:45, 5 февраля 2020

Данный алгоритм использует ту же идею, что и алгоритм Эдмондса-Карпа, мы будет пускать поток только вдоль кратчайших путей.

Определение:
Слоистая сеть —это сеть состоящая только из таких рёбер $(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

@@ Строка 14: / Строка 14: @@
 {{Утверждение
 |Утверждение=После каждой итерации алгоритма расстояние до стока строго увеличивается
-|Доказательство=Тривиально
+|Доказательство=Как известно, при продлевании потока вдоль кратчайшего пути не существует вершины, до которой расстояние от истока бы уменьшилось ([[Алгоритм Эдмондса-Карпа|Лемма о кратчайшем увеличивающем пути]]). Значит остается доказать, что расстояние до стока не осталось прежним.
-}}
+Докажем это от противного, пусть расстояние не изменилось. Рассмотрим кратчайший путь $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)$.