147
правок
Изменения
→Улучшение пути
==Улучшение пути==
Путь из <tex>S</tex> в <tex>T</tex> найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:
Пусть после <tex>(2)</tex> запроса появилось нулевое ребро. Запрос минимума от <tex>S</tex> до корня будет возвращать <tex>0</tex>. Поэтому, такие ребра нужно отрезать, выполнив <tex>(3)</tex> запрос по этому ребру.