Алгоритм Эдмондса-Карпа

Данный алгоритм очень похож на алгоритм Форда-Фалкерсона и отличается только тем, что мы будем пускать поток не по произвольному увеличивающему пути, а по кратчайшему. Для этого просто будем вместо $dfs$ использовать $bfs$.

Алгоритм остается корректным по тем же причинам, что и алгоритм Форда-Фалкерсона. Остается только оценить время работы.

Немного теории

Утверждение: (Лемма о кратчайшем увеличивающем пути)
Если $P$ - кратчайший увеличивающий путь в сети G, то после пускания потока вдоль пути $P$, $\forall{v} : d(v) <= d_f(v)$, где $d(v)$ - расстояние от истока до $v$ в сети $G$, а $d_f(v)$ - расстояние от $s$ до $v$ в $G_f$. То есть расстояние не может уменьшиться.

Доказательство:
Рассмотрим вершины, для которых $d > d_f$. Возьмем среди них вершину $v$, с минимальным $d_f$. Тогда существует вершина $u$, что $d_f(u) + 1 = d_f(v)$ и при этом существует ребро $(u, v)$. Это вершина предок $v$ на кратчайшем пути от истока в $G_f$. Так как $d_f(u) < d_f(v)$, а $v$ - вершина с минимальным $d_f$ из тех, для которых $d > d_f$ следует, что $d(u) <= d_f(u)$.

Рассмотрим два случая:

Ребро $(u, v)$ было в $G$, тогда $d(v) = d(u) + 1 \leq d_f(u) + 1 = d_f(v) \Rightarrow d(v) \leq d_f(v)$ - противоречие
Ребро $(u, v)$ не было в $G$, но ребро появилось в $G_f$, а значит поток был пущен по ребру $(v, u)$, но мы пускали поток по кратчайшему пути, а значит: $d(v) + 1 = d(u)$. Тогда $d_f(v) < d(v) + 1 = d(u) \leq d_f(u)$, значит $d_f(v) < d_f(u)$, что противоречит $d_f(v) = d_f(u) + 1$ - противоречие

Утверждение: (Лемма о критическом ребре)
Пусть P - кратчайший путь из $s$ в $t$, назовём ребро $(v, u)$ критическим если $c(v, u)$ - минимальна на всем пути $P$. Покажем, что ребро может становится критическим не более $O(V)$ раз.

Доказательство остаётся читателю в качестве упражнения

Оценка времение работы

Каждое ребро может становиться критическим $O(V)$ раз. Суммарно все ребра становятся критическими $O(VE)$ раз. После пускания потока вдоль кратчайшего пути, хотя бы одно ребро становится критическим и пропадает из остаточной сети, значит всего понадобится $O(VE)$ поисков кратчайших путей. Поиск кратчайшего пути мы делаем с помощью $bfs$ следовательно время работы алгоритма $O(VE^2)$.

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana