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

Алгоритм

Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона, в которой в качестве дополняющего пути выбирается кратчайший по ребрам путь в остаточной сети (длины всех ребер равны [math]1[/math]).

Описание

1. Положим все потоки равными нулю. Остаточная сеть изначально совпадает с исходной сетью.
2. В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся.
3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
   1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью [math]\mathrm{c_{min}}[/math].
   2. Для каждого ребра на найденном пути увеличиваем поток на [math]\mathrm{c_{min}}[/math], а в противоположном ему — уменьшаем на [math]\mathrm{c_{min}}[/math].
   3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
4. Возвращаемся на шаг 2.

Сложность

Сложность алгоритма Эдмондса-Карпа равна [math]O(VE^2)[/math].

Псевдокод

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

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла [math]\mathrm {while}[/math] можно выполнить за время [math]O(E)[/math]. Инициализация в процедуре Edmonds Karp производится за [math]O(E)[/math], следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет [math]O(V E^2)[/math].

Пример графа на котором алгоритм дает плохую асимптотику

«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа

Заметим также, что сущетсвует сеть грибок на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет [math]\Omega(V E^2)[/math]. Рассмотрим этот случай более подробно. Норман Заде (англ. Norman Zadeh) описал примеры, которые позволяют добиться асимптотики [math]\Omega(V^3)[/math]. В нашем примере алгоритм выполнит [math]\Omega(V^3)[/math] улучшений пути вне зависимости от выбора этого пути. Разделим все вершины (за исключением [math]s[/math] и [math]t[/math]) на подмножества:

• [math]S={s_1,\ldots,s_k}[/math] — множество вершин, в которые входят ребра из [math]s[/math] с пропускной способностью [math]k[/math],
• [math]T={t_1,\ldots,t_k}[/math] — множество вершин, из которых исходят ребра в [math]t[/math] с пропускной способностью [math]k[/math],
• [math]U={u_1,\ldots,u_{2p}}[/math] — множество вершин, достижимых из [math]s[/math] по ребрам с бесконечной пропускной способностью (не используя иные ребра),
• [math]V={v_1,\ldots,v_{2p}}[/math] — множество вершин, из которых можно достигнуть [math]t[/math] по ребрам с бесконечной пропускной способностью (не используя иные ребра).

[math]S[/math] и [math]T[/math] содержат [math]k[/math] вершин, [math]U[/math] и [math]V[/math] содержат [math]2p[/math] вершин. Где [math]k[/math] и [math]p[/math] фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества [math]S[/math] и [math]T[/math]), имеет единичную пропускную способность; пунктирные ребра имеют бесконечную пропускную способность; остальные ребра(в форме дуги) имеют пропускную способность [math]k[/math]. В начале работы алгоритма путь увеличиться [math]k^2[/math] раз по пути ([math]s[/math], [math]S[/math], [math]T[/math], [math]t[/math]), длина которого равна трем. После этого остаточная сеть будет содержать обратные ребра из [math]T[/math] в [math]S[/math], и алгоритм выберет еще [math]k^2[/math] путей [math](s, u_1, u_2, T, S, v_2, v_1, t)[/math] длины [math]7[/math], затем путь [math](s, u_1, u_2, u_3, u_4, S, T, v_4, v_3, v_2, v_1, t)[/math] длины [math]11[/math] и так далее.

Число вершин в сети: [math]n = 2\cdot k + 4\cdot p + 2[/math].

Число ребер: [math] m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p[/math].

Нетрудно заметить, что число удлиняющих путей [math] a = k^2\cdot (p+1)[/math]. Возьмем [math]p[/math] равным [math]k - 1[/math]. В этом случае [math]n = 6 \cdot k - 2[/math] и [math]a = k^3[/math]. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.

Изначальный граф, нулевой поток

Граф после [math]k^2[/math] поисков пути(в нашем случае [math]k^2 = 4[/math]).
Ребра из между множествами [math]S[/math] и [math]T[/math] полностью насыщены. Поток равен четырем

Алгоритм нашел путь через ребра бесконечной вместимости, совершив еще [math]k^2 = 4[/math] шагов. Поток равен восьми

Источники информации

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