Алгоритмы и структуры данных

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

Алгоритм для решения проблемы максимального потока в сети. Он основан на идее увеличения потока путем нахождения дополняющих путей в остаточной сети.

Алгоритм:
1. Инициализируем максимальный поток равным нулю.
2. Пока существует дополняющий путь в остаточной сети:
- Находим дополняющий путь с помощью любого подходящего алгоритма поиска в глубину или поиска в ширину.
- Находим минимальную пропускную способность на этом пути.
- Увеличиваем поток вдоль этого пути на минимальную пропускную способность.
- Обновляем остаточную сеть, уменьшая пропускные способности на прямых ребрах и увеличивая на обратных ребрах.
3. Возвращаем полученный максимальный поток.

Сложность: O(E*V^2)

www.tgoop.com/the_algorithms/4613

6.4K viewsNov 25, 2023 at 09:03

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

Алгоритм для решения проблемы максимального потока в сети. Он основан на идее увеличения потока путем нахождения дополняющих путей в остаточной сети.

Алгоритм:
1. Инициализируем максимальный поток равным нулю.
2. Пока существует дополняющий путь в остаточной сети:
- Находим дополняющий путь с помощью любого подходящего алгоритма поиска в глубину или поиска в ширину.
- Находим минимальную пропускную способность на этом пути.
- Увеличиваем поток вдоль этого пути на минимальную пропускную способность.
- Обновляем остаточную сеть, уменьшая пропускные способности на прямых ребрах и увеличивая на обратных ребрах.
3. Возвращаем полученный максимальный поток.

Сложность: O(E*V^2)

BY Алгоритмы и структуры данных