Изменения

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

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

171 байт добавлено, 20:29, 4 января 2016
м
Улучшение пути
* При помощи <tex>(2)</tex> запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(4)</tex> запрос по этому ребру. Стоит заметить, что нулевых ребер может получиться несколько, в случае нескольких минимумов.
===Итоговый алгоритм===
147
правок

Навигация