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

В информатике алгоритм Эдмондса-Карпа представляет собой реализацию метода Форда-Фалкерсона для вычисления максимального потока в потоковой сети во времени. Алгоритм был впервые опубликован Ефимом Диницем (чье имя также транслитерируется как «EA Dinic», в частности, как автор его ранних статей) в 1970 году ^[1]^[2] и независимо опубликован Джеком Эдмондсом и Ричардом Карпом в 1972 году. ^[3] Алгоритм Диника включает дополнительные методы, которые сокращают время выполнения до . ^[2] ${\ Displaystyle О (| В | | Е | ^ {2})}$ ${\ Displaystyle О (| В | ^ {2} | Е |)}$

Алгоритм идентичен алгоритму Форда-Фалкерсона , за исключением того, что порядок поиска при нахождении увеличивающего пути определен. Найденный путь должен быть кратчайшим путем с доступной пропускной способностью. Это можно найти с помощью поиска в ширину , где мы применяем вес 1 к каждому ребру. Время работы находится, показывая, что каждый увеличивающий путь может быть найден за время, что каждый раз, когда хотя бы одно из ребер становится насыщенным (ребро с максимально возможным потоком), что расстояние от насыщенного ребра до источника вдоль увеличивающего пути должен быть длиннее, чем в прошлый раз, когда он был насыщен, и что длина не более ${\ Displaystyle О (| В | | Е | ^ {2})}$ ${\ Displaystyle О (| Е |)}$ ${\ Displaystyle Е}$ ${\ Displaystyle | В |}$ . Другое свойство этого алгоритма состоит в том, что длина кратчайшего увеличивающего пути монотонно возрастает. Доступное доказательство есть во Введении в алгоритмы . ^[4]

В парах , написанных по краям, - текущий поток, а - пропускная способность. Остаточная мощность от до равна общей мощности за вычетом уже использованного потока. Если чистый поток из в отрицательный, он вносит свой вклад в остаточную мощность. ${\ Displaystyle ф / с}$ ${\ Displaystyle е}$ ${\ Displaystyle с}$ ${\ Displaystyle ты}$ ${\ Displaystyle v}$ ${\ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$ ${\ Displaystyle ты}$ ${\ Displaystyle v}$