tgoop.com/the_algorithms/4634
Last Update:
Алгоритм масштабирования пропускной способности
Алгоритм для решения проблемы максимального потока в графе. Он основан на алгоритме Форда-Фалкерсона.
Алгоритм:
1. Найдите начальный поток в графе, например, с использованием алгоритма Форда-Фалкерсона.
2. Инициализируйте пропускную способность масштабирования - это максимальная пропускная способность ребер в графе.
3. Пока пропускная способность масштабирования больше нуля:
- Выполните DFS (поиск в глубину) или BFS (поиск в ширину) для нахождения увеличивающего пути от источника к стоку в графе с пропускной способностью, которая превышает текущую пропускную способность масштабирования.
- Если найден увеличивающий путь:
- Найдите минимальную пропускную способность c увеличивающего пути.
- Увеличьте поток по увеличивающему пути на значение c.
- Уменьшите пропускную способность масштабирования на значение c.
4. Верните итоговый поток в графе.
Сложность: O((V+E) * logC), где C - максимальная пропускная способность ребер в графе
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4634