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

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

Алгоритм

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

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

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