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

Данный алгоритм очень похож на алгоритм Форда-Фалкерсона и отличается только тем, что мы будем пускать поток не по произвольному увеличивающему пути, а по кратчайшему. Для этого просто будем вместо $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)$ раз.

Доказательство:
Рассмотрим критическое ребро $(v, u)$ принадлежащее кратчайшему пути $P$. Так как $P$ - кратчайший путь $d_0(v) + 1 = d_0(u)$. После пускания потока вдоль $P$ ребро $(v, u)$ пропадает из остаточной сети и что бы оно там появилось снова мы должны пустить поток вдоль обратного ему ребра $(u, v)$. В данном алгоритме мы всегда пускаем поток вдоль кратчайшего пути, а что бы ребро $(u, v)$ принадлежало ему должно выполняться равенство: $d_1(u) + 1 = d_1(v)$. По лемме о кратчайшем увеличивающем пути: $d_0(u) <= d_1(u)$, а значит: $d_0(v) = d_0(u) - 1 <= d_1(u) - 1 = d_1(v) - 2 \Rightarrow d_0(v) <= d_1(v) - 2$, то есть расстояние до $v$ строго увеличилось. Так как расстояние не может превышать $|V|$ ребро $(v, u)$ не может становиться критическим больше чем $O(V)$ раз.

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

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

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

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