Изменения

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

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

1 байт добавлено, 20:26, 4 января 2016
м
Поиск пути
* '''Шаг 1'''. Пусть <tex>U</tex> {{---}} корень дерева, в котором лежит <tex>S</tex>.
* '''Шаг 2'''. Если вершина <tex>U</tex> совпала с вершиной <tex>T</tex> переходим к '''шагу 6''', иначе к '''шагу 3'''.
* '''Шаг 3'''. Выберем следующее ненасыщеюнное исходящее ребро. Если ребра нет {{---}} переходим к '''шагу 7'''.Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{---}} больше его не рассматриваем.
* '''Шаг 4'''. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>. Подвесим корень <tex>U</tex> через это ребро к вершине <tex>V</tex>, выполнив <tex>(4)</tex> запрос.
* '''Шаг 5'''. В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра. Переходим к '''шагу 1'''.
147
правок

Навигация