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

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

Алгоритм

Для заданной транспортной сети [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 \leadsto t[/math] путей в [math]G_f[/math]. То для всех вершин [math]v \in V[G]\backslash{s,t}[/math] длина кратчайшего пути [math]\delta_f(s, v)[/math] в остаточной сети [math]G_f[/math] монотонно возрастает с каждым увеличением потока.

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

[math]\triangleright[/math]

Пусть [math]f\lt Предположим, что для некоторой вершины \lt tex\gt v \in V[G] \backslash {s,t}[/math] существует такое увеличение потока, котрое приводит к уменьшению длины кратчайшего пути.

[math]\triangleleft[/math]