#5. Алгоритм Форда-Фалкерсона | Алгоритмы на Python

• Алгоритм предложен в 1954 году учёными Фордом и Фалкерсоном.  

• Определяет максимальную пропускную способность потока в направленном графе.  

• Вес дуги в графе представляет возможный поток, который может быть потоком жидкости, газа или информации.  

• Чем больше вес дуги, тем выше её пропускная способность.  

• Значение веса может быть любым целым неотрицательным числом.  

• Необходимо выбрать вершину истока и вершину стока.  

• Движение возможно только в направлении стрелок, обратное перемещение невозможно.  

• Минимальное значение веса дуги равно единице.  

• Из вершины 1 исходит две дуги с весом 7 и 7, суммарный входной поток не может превышать 14 единиц.  

• У стока входные дуги составляют 8 и 4 единицы, в сумме 12 единиц.  

• Максимальный поток для этого графа равен 12 единицам.  

• Находим маршруты от истока к стоку.  

• Максимальный поток соответствует самому узкому месту пути.  

• Отмечаем максимальный поток для каждой дуги на графе.  

• Рассматриваем следующий маршрут из первой вершины через третью, пятую и шестую.  

• Максимальный поток равен 4 единицам.  

• Добавляем ещё один маршрут, увеличивая суммарный поток до 11 единиц.  

• Обнаружена ошибка: расчёт занижает реальную пропускную способность.  

• Добавляем ненасыщенный маршрут, двигаясь против стрелок.  

• Суммарный поток увеличивается до 12 единиц.  

• Если в маршруте встречается противоположная дуга, величину потока уменьшаем.  

• Для остальных дуг значение потока увеличиваем.  

• Рассматриваем граф с начальными значениями потоков.  

• Вершина 1 — исток, вершина 5 — сток.  

• На первой итерации выбираем вершину с наибольшим потоком и повторяем операцию для следующей вершины.  

• Выбираем вершину 1 как текущую и формируем множество вершин, которые можно перейти из неё.  

• Выбираем вершину  

• Из вершины 3 можно пройти в вершины 4 и 5, но не в 2 из-за нулевого потока.  

• Вершина 5 имеет наибольший вес 20 единиц, поэтому её выбирают для дальнейшего рассмотрения.  

• У вершины 5 ставят метку с текущим потоком 20 единиц и вершиной-источником 3.  

• Максимальный поток определяется как минимальное значение среди значений дуг.  

• Веса дуг пересчитываются по формуле: при движении по стрелке вычитается значение перед дробью и добавляется после, при движении против стрелки знаки меняются на противоположные.  

• Пример пересчёта: вес дуги становится 10,20 после вычитания 20 из 30 и добавления 20 к 0.  

• Убираются метки с вершин, и процесс повторяется с вершины 1.  

• Выбирается вершина 2 с максимальным потоком 10.  

• От вершины 2 можно двигаться к вершине 3 или 5, выбирается вершина 3.  

• От вершины 3 можно двигаться к вершине 4.  

• Максимальный поток для нового маршрута составляет 10 единиц.  

• Пересчитываются веса дуг с учётом нового максимального потока.  

• Начинается новая итерация с вершины 1.  

• Выбирается вершина 2, затем 3.  

• Если поток в направлении к вершине 4 или 5 равен нулю, вершина удаляется из рассмотрения и процесс повторяется с предыдущей вершины.  

• Алгоритм Форда-Фалкерсона завершает работу, перебрав все варианты.  

• Максимальная величина потока по сети составляет 60 единиц.  

• Сумма потоков для каждого маршрута равна 60 единицам.  

• Программа доступна на GitHub для скачивания и экспериментов.  

• Список `v` определяет конфигурацию графа: первые два значения — это вершины, третье значение — направление движения по стрелке или против неё.  

• Стрелка от первой вершины ко второй указывает направление движения.  

• Матрица `v` пересчитывается на каждой итерации.  

• Определены переменные: `n` — число вершин, `s` — вершина истока, `t` — вершина стока, `t_s` — метка истока.  

• `f` — список максимальных потоков для каждого найденного маршрута.  

• Итерации начинаются с истока, счётчик `j` проверяет наличие следующих вершин.  

• Функция `get_max_vertex` выбирает следующую вершину с наибольшей пропускной способностью.  

• Если счётчик `j` равен `-1`, это означает тупик.  

• При тупике на истоке алгоритм завершается.  

• При локальном тупике используется индекс предыдущей вершины для выхода из него.  

• Сохраняется текущий поток для фрагмента ребра.  

• Добавляются метки маршрута в список `t`: текущая пропускная способность, индекс текущей и предыдущей вершины.  

• Обновляется множество просмотренных вершин.  

• Если текущая вершина равна истоку, добавляется максимальное значение потока маршрута в коллекцию `f`.  

• Пересчитываются веса дуг с помощью функции `update_v`.  

• Завершается цикл, начинается новая итерация.  

• Инициализируются начальные значения переменных.  

• Процесс поиска маршрута повторяется до исчерпания возможностей.  

• Максимальный поток через граф вычисляется суммированием всех максимальных потоков для каждого маршрута.  

• Пример: максимальный поток равен 60, что соответствует рассмотренному примеру.