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

Эта статья находится в разработке!

Алгоритм

Для заданной транспортной сети [math]G(V, E, c)[/math] алгоритм Эдмондса-Карпа найходит поток максимальной величины из заданной вершины [math]s[/math] в заданную вершину [math]t[/math] за [math]O(V E^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]

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

Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона. На каждой итерации цикла while поток в графе [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] до которой минимально</tex> и уменьшилось с увеличением потока. Имеем . Рассмотрим путь , являющийся кратчайшим от [math]s[/math] к [math]v[/math] в [math]G'_f[/math]. Тогда верно, что .

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

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

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

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

Теорема:

Пусть для некоторой сети с источником и стоком выполняется алгоритм Эдмондса-Карпа, то общее число итераций цикла while составляет .

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

Рассмотрим множество ребер [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](u, v)[/math]. Это может произойти только в том случае, если ребро [math](u, v)[/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].

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

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

Литература

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

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