Считаем рёбра

Алгоритм Эдмондса-Карпа с обходом в ширину

Шаги алгоритма:

1.

Инициализация: поток для всех рёбер.

2.

Пока существует путь из истока в сток в остаточной сети

• Найти кратчайший путь из в с помощью BFS (обход в ширину).
• Увеличить поток вдоль на величину остаточной пропускной способности
• Обновить остаточную сеть

Корректность:

• Теорема Форда-Фалкерсона: Поток максимален тогда и только тогда, когда в остаточной сети нет дополняющих путей, значит, пока поток не максимален, найдется путь, по которому мы увеличим поток.
• Конечность: При целочисленных пропускных способностях каждый шаг увеличивает поток на целое число. Так как максимальный поток ограничен (например, суммой пропускных способностей рёбер из истока), алгоритм завершится за шагов, где — значение максимального потока, и на каждом шаге мы заупскаем BFS.

Пример несходящегося алгоритма: Рассмотрим сеть с источником стоком рёбрами и пропускными способностями:

а пропускные способности остальных рёбер равны целому числу

Константа удовлетворяет условию:

Используем пути в остаточном графе:

• После шагов и остаточные пропускные способности рёбер имеют вид где

• Цикл из путей может повторяться бесконечно. Полный поток после шага

  

• При бесконечном выполнении поток сходится к:

  

  но максимальный поток равен