Алгоритм Голдберга-Тарьяна
Алгоритм Голдберга-Тарьяна (англ. Goldberg-Tarjan) — алгоритм, решающий задачу нахождения максимального потока в транспортной сети за
. Можно считать модификацией алгоритма Диница.Идея
Вспомним алгоритм Диница. Пусть есть сеть — некоторый ориентированный ациклический граф, , — исток и сток соответственно. Схема Алгоритма Диница :
- При помощи обхода в глубину находим путь из в .
- Находим ребро с минимальной пропускной способностью
- Вдоль пути увеличиваем поток на минимальную пропускную способность
Попытаемся ускорить процесс поиска пути из
в . Для этого, для каждой вершины зафиксируем какое-либо, не более, чем одно, исходящее из нее ребро. Граф ацикличен, значит зафиксированные ребра будут образовывать лес корневых деревьев. Корнем каждого дерева будет вершина, у которой нет зафиксированного ребра. В каждой вершине будем дополнительно хранить остаточную пропускную способность исходящего зафиксированного ребра.Пусть каждое дерево поддерживает следующие операции:
- Вычислить минимум на пути от вершины до корня (1).
- Прибавить константу к числам на пути от вершины до корня (2).
- Отрезать поддерево по ребру. Отрезанное поддерево отделяется и существует независимо от исходного дерева (3).
- Подвесить дерево. Пусть есть дерево с корнем , дерево с вершиной . Операция позволяет Создать ребро из в и тем самым подвесить дерево к вершине (4).
Заметим, что именно эти операции поддерживает Link-Cut tree и умеет их выполнять за .
Поиск пути
Научимся находить путь из
в в описанной выше сети при помощи леса корневых деревьев. Будем отдельно хранить дерево с потоками и дерево с пропускными способностями.Пусть
— корень дерева, в котором лежит .- Заметим, что если , лежат в одном дереве, то путь ищется легко. Это путь по дереву до корня.
- Если , лежат в разных деревьях. Просмотрим все ненасыщенные исходящие ребра. Будем рассматривать их также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло — больше его не рассматриваем. Пусть просматриваем какое-то ненасыщенное ребро, ведущее в некоторую вершину :
- Подвесим корень через это ребро к вершине V (Операция 3).
- В записываем число, равное остаточной пропускной способности ребра.
- Будем повторять, пока и не окажутся в одном дереве.
Улучшение пути
Путь из
в найден, теперь научимся улучшать путь. Нужно обновить значения пропускных способностей и потоков через вершины этого пути. Тогда:- При помощи запроса можно найти узкое место (ребро с минимальной остаточной пропускной способностью) на этом пути и его пропускную способность.
- При помощи запроса можно вычесть из всех ребер на этом пути пропускную способность узкого места, а также, прибавить ее к потоку.
Пусть после
запроса появилось нулевое ребро. Запрос минимума от до корня будет возвращать . Поэтому, такие ребра нужно отрезать, выполнив запрос по этому ребру.Алгоритм
Объединим вышесказанное в алгоритм Голдберга-Татьяна. Пусть дана сеть. Требуется в этой сети найти поток
максимальной величины.- Для каждого ребра данной сети зададим .
- Пока есть путь из
- Выполняем запрос , находим узкое место и пропускную способность.
- Обновляем значения потока и пропускной способности при помощи запроса .
- Обрезаем нулевые ребра при помощи запроса .
в :
Время работы
Linking-Cutting Tree выполняет все вышеописанные запросы за , оценим время работы алгоритма.
Очевидно, что просмотров ребер суммарно
, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:- Просматриваемое ребро насыщено.
- Дерево разрезается по нулевому ребру.
- Ребро не лежит в сети кратчайших путей.
На каждый просмотр тратится не
а , потому что перед тем, как посмотреть на следующее ребро делается запрос. Значит время работы этой части — .Следующий шаг в алгоритме Диница — сумма длин путей. Раньше считалось за
, так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм .Тогда имеем ассимптотику
. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику