Изменения

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

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

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

Навигация