Главная › Новости

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

Опубликовано: 23.09.2017

EDMONDS KARP ALGORITHM 1 mp4 10 wmv

Материал из Википедии — свободной энциклопедии

Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети . Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время Невозможно разобрать выражение (Выполняемый файл <code>texvc</code> не найден; См. math/README — справку по настройке.): O(VE^2) . Впервые был опубликован в 1970 году советским учёным Е. А. Диницом . Позже, в 1972 году , был независимо открыт Эдмондсом и Карпом .

Насыщение сети

Алгоритм

Алгоритм Эдмондса — Карпа — это вариант алгоритма Форда — Фалкерсона , при котором на каждом шаге выбирают кратчайший дополняющий путь из Невозможно разобрать выражение (Выполняемый файл <code>texvc</code> не найден; См. math/README — справку по настройке.): s в Невозможно разобрать выражение (Выполняемый файл <code>texvc</code> не найден; См. math/README — справку по настройке.): t в остаточной сети (полагая, что каждое ребро имеет единичную длину). Кратчайший путь находится поиском в ширину .

Алгоритм Форда-Фалкерсона

Описание

Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью. В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью ) максимально возможный поток: На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью Невозможно разобрать выражение (Выполняемый файл <code>texvc</code> не найден; См. math/README — справку по настройке.): c_\min . Для каждого ребра на найденном пути увеличиваем поток на Невозможно разобрать выражение (Выполняемый файл <code>texvc</code> не найден; См. math/README — справку по настройке.): c_\min , а в противоположном ему — уменьшаем на Невозможно разобрать выражение (Выполняемый файл <code>texvc</code> не найден; См. math/README — справку по настройке.): c_\min . Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его. Возвращаемся на шаг 2.

Чтобы найти кратчайший путь в графе, используем поиск в ширину :