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

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

Алгоритм

Идея

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

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

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

Желтым выделены зафиксированные ребра. Тогда [math]T[/math] — корень дерева

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

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

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

Поиск пути

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

• Начало.
• Шаг 1. Пусть [math]U[/math] — корень дерева, в котором лежит [math]S[/math].
• Шаг 2. Если вершина [math]U[/math] совпала с вершиной [math]T[/math] переходим к шагу 6, иначе к шагу 3.
• Шаг 3. Выберем следующее ненасыщенное исходящее ребро. Если ребра нет — переходим к шагу 7. Ребра рассматриваем также, как и в алгоритме Диница, с глобальным итератором. Т.е начинать просмотр будем с последнего подошедшего ребра. Если ребро не подошло — больше его не рассматриваем.
• Шаг 4. Пусть просматриваем ненасыщенное ребро, ведущее в некоторую вершину [math]V[/math]. Подвесим корень [math]U[/math] через это ребро к вершине [math]V[/math], выполнив [math](4)[/math] запрос.
• Шаг 5. В [math]U[/math] записываем число, равное остаточной пропускной способности ребра. Переходим к шагу 1.
• Шаг 6. Возвращаем найденный путь.
• Шаг 7. Пути из [math]S[/math] в [math]T[/math] нет.
• Конец.

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

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

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

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

Итоговый алгоритм

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

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

Время работы

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

Очевидно, что просмотров ребер суммарно [math]O(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], так как на каждый путь обход в глубину тратил время, пропорциональное длине этого пути. Сейчас тратится только [math]O(\log(V))[/math] на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм [math]O(\log(V))[/math].

Тогда имеем ассимптотику [math]O(E\log(V) + V \log(V)) = O((V + E) \log(V))[/math]. И, суммарно, если подставить в алгоритм Диница будем иметь ассимптотику [math]O(VE \log(V)) [/math].

См. также

• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
• Алоритм Эдмондса-Карпа
• Алгоритм масштабирования потока
• Метод проталкивания предпотока

Источники информации

• Lektorium — Лекция А.С. Станкевича