Алгоритм Форда-Фулкерсона решает проблему максимального потока от исходного узла к приемному узлу.

Глядя на псевдокод, мы можем в некоторой степени его понять. Но давайте сегодня полностью забьем гвоздь на примере.

Мы хотим найти максимальный поток от исходного узла A до приемного узла D. При визуальном осмотре максимальный расход составляет 2000.

Но давайте попробуем запустить алгоритм Форда-Фулкерсона и посмотрим, как он систематически приводит к одному и тому же результату.

Мы инициализируем Graph G как:

Итерация 1

Остаточный граф, Gf:

Предположим, что алгоритм Форда-Фулкерсона использует поиск в глубину и пытается достичь узлов в алфавитном порядке, если это возможно. Следовательно, путь от A к D есть A → B → C → D. Ребро с минимальной пропускной способностью на пути равно (B, C), которое = 1.

Обновляем потоки в G, давая:

Итерация 2

Используя обновленную G, мы формируем обновленный остаточный график:

Путь от A к D теперь равен A → B → D, поскольку нет исходящего ребра от B до C. Ребро с минимальной пропускной способностью на пути равно (A, B), что = 999.

Обновляем потоки в G, давая:

Итерация 3

Используя обновленную G, формируем Gf:

Путь от A к D теперь будет A → C → B → D, поскольку нет ребра от A до B. Ребро с минимальной пропускной способностью на пути - (C, B), которое = 1.

Обновляя G, получаем:

Обратите внимание, что край (B, C) в G имеет противоположное направление по отношению к ребру (C, B) в Gf, которое является частью пути от A до D. Следовательно, мы вычитаем поток из Г.

Итерация 4

Используя обновленную G, формируем новую Gf:

Остается один путь из A в D, который проходит через C. Путь A → C → D. Край минимальной пропускной способности на пути равен (A, C) или (C, D), что равно 999.

Обновляя G, получаем:

Итерация 5

Из G формируем Gf:

Заметим, что путей от A к D больше нет! Следовательно, мы завершаем наш алгоритм.

Следовательно, исходя из графика G в итерации 4, максимальный поток = сумма потока от входящих ребер до приемного узла D = 1000 + 1000 = 2000. Это наш ответ, и мы можем его вернуть!

Вы теперь лучше понимаете алгоритм? Попробуйте применить его на разных примерах или один и тот же пример самостоятельно!