Изменения
Нет описания правки
'''Алгоритм Голдберга-Тарьяна''' (англ . ''Goldberg-Tarjan'') {{--- }} алгоритм, решающий задачу нахождения максимального потока в транспортной сети за <tex>O(VE \log(V))</tex>. Можно считать модификацией Алгоритма алгоритма Диница.
==Идея==
Вспомним [[Схема алгоритма Диница|Алгоритм алгоритм Диница]]. Пусть есть сеть <tex>G^0_f </tex> {{---}} некоторый ориентированный ациклический граф, <tex>S</tex>, <tex>T</tex> {{---}} исток и сток соответственно. Схема Алгоритма Диница :
# При помощи [[Обход в глубину, цвета вершин|обхода в глубину]] находим путь из <tex>S</tex> в <tex>T</tex>.
# Находим ребро с минимальной пропускной способностью
# Подвесить дерево. Пусть есть дерево с корнем <tex>A</tex>, дерево с вершиной <tex>B</tex>. Операция позволяет Создать ребро из <tex>A</tex> в <tex>B</tex> и тем самым подвесить дерево к вершине.
Заметим, что именно эти операции поддерживает [[Link-Cut Tree|LinkingLink-Cutting TreeCut tree]] и умеет их выполнять за <tex>O(\log(N))</tex>.
==Поиск пути==
* Заметим, что если <tex>S</tex>, <tex>T</tex> лежат в одном дереве, то путь ищется легко. Это путь по дереву до корня.
* Если <tex>S</tex>, <tex>T</tex> лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в Алгоритме алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло {{- --}} больше его не рассматриваем. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину <tex>V</tex>:
# Подвесим корень <tex>U</tex> через это ребро к вершине V (Операция 3).
#В <tex>U</tex> записываем число, равное остаточной пропускной способности ребра.
==Алгоритм==
Объединим вышесказанное в Алгоритм алгоритм Голдберга-Татьяна.
Пусть дана сеть. Требуется в этой сети найти поток <tex>f(S, T) </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(V))</tex> на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм <tex>O(\log(V))</tex>.
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в Алгоритм алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(V)) </tex>
== Источники ==
