Алгоритм Форда-Фулкерсона решает проблему максимального потока от исходного узла к приемному узлу.
Глядя на псевдокод, мы можем в некоторой степени его понять. Но давайте сегодня полностью забьем гвоздь на примере.
Мы хотим найти максимальный поток от исходного узла 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. Это наш ответ, и мы можем его вернуть!
Вы теперь лучше понимаете алгоритм? Попробуйте применить его на разных примерах или один и тот же пример самостоятельно!