Главная
›
Новости
Алгоритм Эдмондса — Карпа
Опубликовано: 24.09.2017
Edmonds Karp AlgorithmМатериал из Википедии — свободной энциклопедии
Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети . Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время <math>O(VE^2)</math>. Впервые был опубликован в 1970 году советским учёным Е. А. Диницом . Позже, в 1972 году , был независимо открыт Эдмондсом и Карпом .
Алгоритм
Алгоритм Эдмондса — Карпа — это вариант алгоритма Форда — Фалкерсона , при котором на каждом шаге выбирают кратчайший дополняющий путь из <math>s</math> в <math>t</math> в остаточной сети (полагая, что каждое ребро имеет единичную длину). Кратчайший путь находится поиском в ширину .
Лекция 3: Максимальный поток
Описание
Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся.
Пускаем через найденный путь (он называется
увеличивающим путём или
увеличивающей цепью ) максимально возможный поток:
На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью <math>c_\min</math>.
Для каждого ребра на найденном пути увеличиваем поток на <math>c_\min</math>, а в противоположном ему — уменьшаем на <math>c_\min</math>.
Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
Возвращаемся на шаг 2.
Чтобы найти кратчайший путь в графе, используем поиск в ширину :
Edmonds Karp Algorithm to find the Max Flow