Авторизация
Забыли пароль? Введите ваш е-мейл адрес. Вы получите письмо на почту со ссылкой для восстановления пароля.
После регистрации вы сможете задавать вопросы и писать свои ответы, получая за это бонусы. Все остальные функции на сайте доступны без регистрации.
Вы должны войти или зарегистрироваться, чтобы добавить ответ и получить бонусы.
Для поиска максимального потока в графе можно использовать алгоритм Форда-Фалкерсона или алгоритм Эдмондса-Карпа.
Алгоритм Форда-Фалкерсона:
1. Инициализируем поток в графе нулевыми значениями.
2. Пока существует путь от источника к стоку в остаточной сети:
— Находим минимальную пропускную способность ребер на этом пути.
— Увеличиваем поток на этой величине.
— Уменьшаем пропускную способность ребер на этом пути на величину потока.
3. Возвращаем суммарный поток из источника.
Алгоритм Эдмондса-Карпа:
1. Инициализируем поток в графе нулевыми значениями.
2. Пока существует путь от источника к стоку в остаточной сети:
— Находим кратчайший путь от источника к стоку в остаточной сети с помощью алгоритма поиска в ширину (BFS).
— Находим минимальную пропускную способность ребер на этом пути.
— Увеличиваем поток на этой величине.
— Уменьшаем пропускную способность ребер на этом пути на величину потока.
3. Возвращаем суммарный поток из источника.
Оба алгоритма работают за время O(E * |f*|), где E — количество ребер в графе, а |f*| — величина максимального потока.