Алгоритм Форда–Фалкерсона: как найти максимальный поток в сети (для начинающих)

Привет, будущие инженеры и программисты! Сегодня мы разберём классический алгоритм Форда–Фалкерсона — дедушку всех алгоритмов максимального потока. Если алгоритм Диница — это современный спорткар, то Форд–Фалкерсон — это надёжная "классика", которая учит основам и помогает понять суть задачи.
Представьте, что вы владелец сети трубопроводов, и вам нужно понять, сколько воды можно прокачать из водохранилища в город. У каждой трубы есть максимальная пропускная способность, и вода может течь только в одном направлении. Ваша задача — найти такой способ распределения воды по трубам, чтобы в город попало максимальное количество воды. Это и есть задача максимального потока!
Читать далее

https://habr.com/ru/articles/927400/?utm_campaign=927400&utm_source=habrahabr&utm_medium=rss