Алгоритм Форда – Фалкерсона

Алгоритм Форда – Фалкерсона

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

Для инициализации алгоритма можно атрибутировать любой поток в графе, следуя простым путям (от источника к приемнику). На следующей диаграмме мы взяли для инициализации путь s-2-3-t.

Алгоритм Форда-Фулкерсона Максимальный поток Проблема максимального потока Минимальный разрез График Увеличение потока
После построения остаточного графа выбирается путь из s в t, если он есть. В противном случае мы имеем максимальный поток. В первом случае новый поток рассчитывается по возрастающему пути, выбранному в графе отклонений: поток возрастающего пути добавляется к существующему потоку, если соответствующая дуга в исходном графе имеет то же направление, что и дуга из исходного графа. график разрыва, в противном случае поток вычитается.Алгоритм останавливается, когда больше нет возрастающего пути.

По графику последнего отклонения можно сформировать разрез. Применяем обход из s, все вершины, которые можно обойти, находятся в множестве S, остальные в множестве T. Действительно, дуги, насыщенные потоками, разрезают граф на два подмножества, и формируют значение разреза.

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

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

Алгоритм Форда-Фалкерсона шаг за шагом

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Начальный поток равен 0. Здесь остаточный граф Gф является копией графа G. Ищем путь из s в t, например s-2-5-t:

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Минимальное значение пути равно 8. Добавляем этот поток из 8 к пути в графе G.

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Напоминаем, что остаточный граф должен показывать обратные дуги (представляющие потоки). Остаточный граф новой итерации выглядит следующим образом:

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Здесь мы выбираем путь s-2-3-5-t, где 2 означает блокировку потока. Когда мы выбираем обратную дугу (поэтому представляющую поток), новый поток в графе G сокращается, как показано на этом новом графе G.

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Значение расхода = 10. И т. д.…

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона
Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Значение расхода = 16

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Выбор обратной дуги (3.2):

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Значение расхода = 18.

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона
Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Значение расхода = 19.

Максимальный поток Максимальный поток Проблема максимального потока График отклонения минимального разреза Увеличение потока Алгоритм Форда-Фулкерсона

Пути из s в t больше нет, мы нашли максимальный поток для этого графа G.

Делиться
ru_RURU
%d такие блоггеры, как: