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

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

Алгоритм

Для заданной транспортной сети [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]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] до которой минимально</tex> и уменьшилось с увеличением потока. Имеем [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) \ge \delta_f(s,u)[/math]. Предположим [math](u, v) \in E_f[/math], тогда [math]\delta_f(s,v) \le \delta_f(s, u) + 1 \le \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 v[/math], из чего получаем [math]\delta_f(s, v) = \delta_f(s, u) - 1 \le \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]

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

Теорема:

Пусть для некоторой сети [math]G(V,E)[/math] с источником [math]s[/math] и стоком [math]t[/math] выполняется алгоритм Эдмондса-Карпа, то общее число итераций цикла while составляет [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]\triangleleft[/math]