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

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

Идея

Вспомним Алгоритм Диница. Пусть есть сеть [math]G^0_f [/math] — некоторый ациклический граф, S, T — исток и сток соответственно. Схема Алгоритма Диница :

1. При помощи обхода в глубину находим путь из S в T.
2. Находим ребро с минимальной пропускной способностью
3. Вдоль пути увеличиваем поток на минимальную пропускную способность

Попытаемся ускорить процесс поиска пути из S в T. Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра. В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.

Пусть каждое дерево поддерживает следующие операции:

1. Вычислить минимум на пути от вершины до корня
2. Прибавить константу к числам на пути от вершины до корня.
3. Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева.
4. Подвесить дерево. Пусть есть дерево с корнем А, дерево с вершиной В. Операция позволяет Создать ребро из A в B и тем самым подвесить дерево к вершине.

Заметим, что именно эти операции поддерживает Linking-Cutting Tree и умеет их выполнять за [math]O(\log(N))[/math]

Поиск пути

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

Пусть U - корень дерева, в котором лежит S.

• Заметим, что если S, T лежат в одном дереве, то путь ищется легко. Это путь по дереву до корня.

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

1. Подвесим корень U через это ребро к вершине V (Операция 3).
2. В U записываем число, равное остаточной пропускной способности ребра.

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

Улучшение пути

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

1. При помощи (1) запроса можно найти узкое место на этом пути и его пропускную способность.
2. При помощи (2) запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.

Пусть после (2) запроса появилось нулевое ребро. Запрос минимума от S до корня будет возвращать 0. Поэтому, такие ребра нужно отрезать, выполнив (4) запрос по этому ребру.

Алгоритм

Объединим вышесказанное в Алгоритм Голдберга-Татьяна. Пусть дана сеть. Требуется в этой сети найти поток [math]f(S, T) [/math] максимальной величины.

1. Для каждого ребра [math](u, v)[/math] данной сети [math]G[/math] зададим [math]f(u, v) = 0[/math]
2. Пока есть путь из S в T:
   1. Выполняем запрос (1), находим узкое место и пропускную способность
   2. Обновляем значения потока и пропускной способности при помощи запроса (2)
   3. Обрезаем нулевые ребра при помощи запроса (4)

Время работы

Linking-Cutting Tree выполняет все вышеописанные запросы за [math]O(\log(N))[/math], оценим время работы алгоритма.

Очевидно, что просмотров ребер суммарно [math]O(\log(E))[/math], как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:

1. просматриваемое ребро насыщено
2. дерево разрезается по нулевому ребру
3. ребро не лежит в сети кратчайших путей

На каждый просмотр тратится не [math]O(1)[/math] а [math]O(\log(V))[/math], потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части — [math]O(E \log(V))[/math].

Следующий шаг в алгоритме Диница - сумма длин путей. Раньше считалось за [math]O(V^2)[/math]. Потому, что на каждый путь DFS тратил время, пропорциональное длине этого пути. Сейчас тратится только [math]O(\log(V))[/math] на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм [math]O(\log(V))[/math].

Тогда имеем ассимптотику [math]O(E\log(V) + V \log(V)) = O(VE \log(VE))[/math]