Изменения

Перейти к: навигация, поиск

Алгоритм Голдберга-Тарьяна

Нет изменений в размере, 20:19, 4 января 2016
Итоговый алгоритм
* '''Шаг 1'''. Для каждого ребра <tex>(u, v)</tex> данной сети <tex>G</tex> зададим <tex>f(u, v) = 0</tex>.
* '''Шаг 2'''. Если есть путь из <tex>S</tex> в <tex>T</tex> {{---}} переходим к '''шагу 3'''.
* '''Шаг 3'''. Выполняем запрос <tex>(1)</tex>запрос, находим путь, узкое место и пропускную способность. Если пропускная способность положительна, переходим к '''шагу 4''', иначе к '''шагу 5'''
* '''Шаг 4'''. ''Улучшение пути''. Обновляем значения потока и пропускной способности при помощи запроса <tex>(2)</tex>.
* '''Шаг 5'''. ''Удаление нулевых ребер''. Обрезаем нулевые ребра при помощи запроса <tex>(3)</tex>запроса. Переходим к '''шагу 2'''.
* Конец
147
правок

Навигация