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

Алгоритм

Для заданной сети $G(V, E, c)$ алгоритм Эдмондса-Карпа найходит поток максимальной величины из заданного истока $s$ в заданный сток $t$ за $O(V E^2)$.

Псевдокод

Edmonds_Karp (G, s, t)
    for (для) каждого ребра $(u,v) \in E[G]$
        do $f[u,v] \leftarrow 0$
           $f[v,u] \leftarrow 0$
    while существует кратчайший путь $p$ из $s$ в $t$ в остаточной сети $G_f$
        do $c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}$
            for (для) каждого ребра $(u,v) \in p$
                do $f[u,v] \leftarrow f[u,v] + c_f(p)$
                   $f[v,u] \leftarrow -f[u,v]$

Корректность алгоритма Эдмондса-Карпа

Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона. На каждой итерации цикла while поток в графе $G$ увеличивается вдоль одного из кратчайших путей в $G_f$ из истока $s$ в сток $t$. Этот процесс повторяется до тех пор пока существует кратчайший $s \leadsto t$ путь в $G_f$. Если в $G_f$ не существует кратчайшего пути из $s$ в $t$, значит не существует никакого вообще никакого $s \leadsto t$ пути в $G_f$ следовательно по теореме Форда-Фалкерсона найденный поток $f$ максимальный. Оценка быстродействия будет проведена далее.

Оценка быстродействия

Лемма:

Если в сети $G(V,E)$ с источником $s$ и стоком $t$ увеличение потока производиться вдоль кратчайших $s \leadsto t$ путей в $G_f$. То для всех вершин $v \in V\backslash{s,t}$ длина кратчайшего пути $\delta_f(s, v)$ в остаточной сети $G_f$ не убывает после каждого увеличения потока.

Доказательство:

$\triangleright$

Предположим противное, пусть существует вершина $v \in V \backslash {s,t}$, что после какого-то увеличения потока длина кратчайшего пути из $s$ в $v$ уменьшилась. Обозначим потоки до и после увеличения соответственно за $f$ и $f'$. Пусть $v$ — вершина, расстояние $\delta'_f(s,v)$ от $s$ до которой минимально</tex> и уменьшилось с увеличением потока. Имеем $\delta'_f(s,v) \lt \delta_f(s,v)$. Рассмотрим путь $p = s \leadsto u \rightarrow v$, являющийся кратчайшим от $s$ к $v$ в $G'_f$. Тогда верно, что $\delta'_f(s, u) = \delta'_f(s,v) - 1$. По выбору $v$ и из предыдущего утверждения получаем, что $\delta'_f (s, u) \ge \delta_f(s,u)$. Предположим $(u, v) \in E_f$, тогда $\delta_f(s,v) \le \delta_f(s, u) + 1 \le \delta'_f(s,u) + 1 = \delta'_f(s, v)$. Это противоречит $\delta'_f(s,v) \lt \delta_f(s,v)$. Пусть $(u,v) \notin E_f$, но известно, что $(u,v) \in E_f$. Появление ребра $(u,v)$ после увеличения потока означает увеличение потока по обратному ребру $(v, u)$. Увеличение потока производится вдоль кратчайшего пути, поэтому кратчайший путь из $s$ в $u$ вдоль которого происходило увеличения выглядит как $s \leadsto v \rightarrow v$, из чего получаем $\delta_f(s, v) = \delta_f(s, u) - 1 \le \delta'_f(s, u) - 1 = \delta'(s, v) - 2$. Данное утверждение противоречит $\delta'_f(s,v) \lt \delta_f(s,v)$. Итак мы пришли к противоречию с существованием вершины $v$, кратчайшее расстояние до которой уменьшилось с увеличением потока.

$\triangleleft$

Опираясь на предшествующую лемму докажем следующую теорему, которая ограничивает сверху число итераций цикла while в алгоритме Эдмондса-Карпа.

Теорема:

Пусть для некоторой сети $G(V,E)$ с источником $s$ и стоком $t$ выполняется алгоритм Эдмондса-Карпа, то общее число итераций цикла while составляет $O(V E)$.

Доказательство:

$\triangleright$

Рассмотрим множество ребер $(u,v)$ остаточной сети $G_f$, принадлежащих увеличивающему пути $p$, таких что $c_f(p) = c_f(u,v)$. Назовем данные ребра критическими. Покажем, что каждое из $|E|$ ребер может становиться критическим не более, чем $|V| - 1$ раз. Заметим, что после увеличения потока вдоль пути $p$ все критические ребра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути — критическое. Рассмотрим две вершины $u$ и $v$ принадлежащие $V$, соединенные некоторым ребром из $E$. Увеличение производиться вдоль кратчайших путей, поэтому если ребро $(u,v)$ становиться критическим в первый раз, верно, что $\delta_f(s,v) = \delta_f(s,u) + 1$. После увеличения потока ребро $(u, v)$ исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен по обратному ребру $(u, v)$. Это может произойти только в том случае, если ребро $(u, v)$ встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети $G$ составлял $f'$, то поскольку увеличение проищводиться вдоль кратчайших путей, верно: $\delta'_f(s,u) = \delta'_f(s, v) + 1$. Согласно лемме $\delta_f(s,v) \le \delta'_f(s,v)$, откуда $\delta'_f(s,u) = \delta(s,v) + 1 \ge \delta_f(s,v) + 1 = \delta_f(s,u) + 2$. Итак в промежутке времени между тем, когда ребро $(u,v)$ становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от $s$ до $u$ увеличивается минимум на $2$. Расстояние $\delta(s,u)$ в начальный момент времени больше либо равно $0$. Среди промежуточных вершин на кратчайшем пути $s \leadsto u$ не могут находиться $s$, $u$ или $t$. Следовательно к тому моменту, когда вершина $u$ станет недостижимой из источника расстояние до нее не превысит $|V| - 2$. Получаем, что ребро $(u, v)$ могло стать критическим не более $(|V| -2)/2 = |V|/2 - 1$ раз. Поскольку в графе не более $O(E)$ пар вершин, между которыми могут существовать ребра в остаточной сети, то общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно $O(V E)$. Поскольку каждый увеличивающий путь, содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет $O(V E)$. На каждой итерации цикла while рассматривается ровно один увеличивающий путь, а так как только такого пути не существует выполнение цикла прервается, то число итераций цикла while также составляет $O(V E)$.

$\triangleleft$

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла while можно выполнить за время $O(E)$. Инициализация в процедуре Edmonds_Karp производиться за $O(E)$, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет $O(V E^2)$. Заметим также, что сущетсвует сеть "грибок" на которое нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет $O(V E^2)$.

Литература

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)