Алгоритм Эдмондса-Карпа — это алгоритм, используемый для решения задачи максимального потока в теории сетевых потоков. Это эффективная реализация метода Форда-Фалкерсона. Алгоритм находит максимальный поток в потоковой сети, который представляет собой максимальный объем потока, который может быть отправлен из исходной вершины в приемную вершину через ребра сети.

Вот пошаговое объяснение алгоритма Эдмондса-Карпа:

1. Инициализировать поток во всех ребрах равным нулю.
2. Пока в остаточном графе существует увеличивающий путь от источника к приемнику:
   a. Найдите дополняющий путь, используя поиск в ширину (BFS).
   b. Определите пропускную способность узкого места расширяющего пути, которая представляет собой минимальную пропускную способность всех ребер пути.
   c. Обновите поток на пути расширения, добавив пропускную способность узкого места к потоку каждого ребра.
   d. Обновите остаточные емкости ребер и их обратных ребер в остаточном графе.
3. Максимальный поток — это сумма значений потока, выходящего из исходной вершины.

Алгоритм Эдмондса-Карпа гарантирует, что максимальный поток может быть найден за временную сложность O(V * E^2), где V — количество вершин, а E — количество ребер в сети.