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

Содержание

1 Алгоритм
- 1.1 Описание
- 1.2 Сложность
2 Псевдокод
3 Корректность алгоритма Эдмондса-Карпа
4 Оценка быстродействия
5 Примечания
6 Источники информации

Алгоритм

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

Описание

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

Сложность

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

Псевдокод

Edmonds_Karp (G, s, t)
    for (для) каждого ребра [math](u,v) \in E[G][/math]
        do [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]
        do [math]c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}[/math]
            for (для) каждого ребра [math](u,v) \in p[/math]
                do [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]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]s[/math] к [math]v[/math] в [math]G'_f[/math]. Тогда верно, что .

По выбору [math]v[/math] и из предыдущего утверждения получаем, что .

Предположим [math](u, v) \in E_f[/math], тогда . Это противоречит .

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

Опираясь на предшествующую лемму, докажем следующую теорему, которая ограничивает сверху число итераций цикла [math]\mathrm {while}[/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](u, v)[/math] исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен по обратному ребру [math](v, u)[/math]. Это может произойти только в том случае, если ребро [math](v, u)[/math] встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети [math]G[/math] составлял [math]f'[/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](|V| -2)/2 = |V|/2 - 1[/math] раз. Поскольку в графе не более [math]O(E)[/math] пар вершин, между которыми могут существовать ребра в остаточной сети, то общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно [math]O(V E)[/math].

Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет . На каждой итерации цикла рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла также составляет .

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

Примечания

↑ Cтатья на TopCoder.com

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

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

[1] Cтатья на TopCoder.com

[1]

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

Содержание