Привет, Хабр! При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.

Постановка задачи

Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокаAв стокF.

Исходный граф
Исходный граф

Как работает сам алгоритм?

Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:

  1. Отправлять определенное количество потока из текущей вершины в соседние.

  2. Возвращать определенное количество потока из соседних вершин в текущую.

  • В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.

  • Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.

  • Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.

  • Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.

  • А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.

  • Возвращаемся обратно к нахождению пути в остаточной сети после модификации.


Разбор конкретного примера

Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.

  • Допустим наш алгоритм нашел следующий путь из вершиныAвFнашей остаточной сети, которая на момент начала, совпадает с исходным графом.

Начальная остаточная сеть
Начальная остаточная сеть
  • Сколько потока можем провести по этому пути???
    - Больше2 ед.мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
    Получаем следующее:

Остаточная сеть после 1-ой итерации
Остаточная сеть после 1-ой итерации

Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.

Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из A в F.

  • Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:

Остаточная сеть после 1-ой итерации
Остаточная сеть после 1-ой итерации

Пропускаем 3 ед. потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:

Остаточная сеть после 2-ой итерации
Остаточная сеть после 2-ой итерации
  • На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:

Остаточная сеть после 2-ой итеации
Остаточная сеть после 2-ой итеации

Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

Остаточная сеть после 3-ей итерации
Остаточная сеть после 3-ей итерации
  • На 4-ой итерации находим следующий путь в остаточной сети:

Остаточная сеть после 3-ей итерации
Остаточная сеть после 3-ей итерации

Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

Итоговая остаточная сеть
Итоговая остаточная сеть

На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.


Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!

Источники