Изменения

'''Алгоритм Голдберга-Тарьяна''' (англ ''Goldberg-Tarjan'') - алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(VE))</tex>. Можно считать модификацией Алгоритма Диница.

 Пусть есть лес корневых деревьев, требуется найти Научимся находить путь из вершины S в вершину Tв описанной выше сети при помощи леса корневых деревьев.Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.

* Заметим, что если S, T лежат в одном дереве, то путь ищется легко. Это путь по дереву до корня. Предположим, что S, T лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в Алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло - больше его не рассматриваем.

* Если S, T лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в Алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло - больше его не рассматриваем. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину V. :# Подвесим корень U через это ребро к вершине V (Операция 3). #В U записываем число, равное остаточной пропускной способности ребра.

* Будем повторять, пока S и T не окажутся в одном дереве.

Linking-Cutting Tree выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма. Очевидно, что просмотров ребер суммарно <tex>O(\log(E))</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:# просматриваемое ребро насыщено# дерево разрезается по нулевому ребру# ребро не лежит в сети кратчайших путей На каждый просмотр тратится не <tex>O(1)</tex> а <tex>O(\log(V))</tex>, потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части {{---}} <tex>O(E \log(V))</tex>.

Просмотров ребра суммарно ОСледующий шаг в алгоритме Диница - сумма длин путей. Раньше считалось за <tex>O(ЕV^2), аналогично алгоритму Диница</tex>. Переход к следующемуПотому, когда смотрим что на ребро и оно насыщено, когда ребро разрезаемкаждый путь DFS тратил время, когда смотрим на ребро и оно не лежит в сети кратчайших путейпропорциональное длине этого пути.На каждый просмотр Сейчас тратится не Отолько <tex>O(\log(1V) а О(log)</tex> на каждый путь. Если путь найден, значит до него дошли, потому что делаем запрос перед тем как посмотреть значит это соответствует одному запросу. Поэтому тратим на следующее ребро. Значит каждый путь тоже логарифм <tex>O(E \log(V))</tex>.

Второй компонент в алг. Диница - сумма длин путей. Была V^2. Почему столько? На каждый путь DFS тратил время, пропорциональное длине этого пути. Но теперь не тратим. Тратим log на каждый путь. Потому что если мы нашли путь, это соответствует тому, что мы дошли до него, т.е одному запросу. Поэтому тратим на каждый путь тоже логарифм. Значит Тогда имеем ассимптотику <tex>O(E \log(V) + V \log(V)).= O(VE \log(VE))</tex>