Изменения

Для заданной Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона, в которой в качестве дополняющего пути выбирается кратчайший по ребрам путь в остаточной сети (длины всех ребер равны <tex>G1</tex>). === Описание === # Положим все потоки равными нулю. Остаточная сеть изначально совпадает с исходной сетью.# В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся.# Пускаем через найденный путь (V, E, cон называется '''увеличивающим путём''' или '''увеличивающей цепью''')максимально возможный поток:## На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью <tex>\mathrm{c_{min}}</tex> алгоритм Эдмондса-Карпа находит .## Для каждого ребра на найденном пути увеличиваем поток максимальной величины из заданного истока на <tex>s\mathrm{c_{min}}</tex> , а в заданный сток противоположном ему — уменьшаем на <tex>t\mathrm{c_{min}}</tex> за .## Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.# Возвращаемся на шаг 2. ===Сложность===Сложность алгоритма Эдмондса-Карпа равна <tex>O(V EVE^2)</tex>.