Алгоритм Суурбалле

Алгоритм Суурбалле — это алгоритм нахождения двух непересекающихся (не имеющих общих рёбер) путей в ориентированном графе с неотрицательными весами, так что оба пути связывают ту же самую пару вершин и имеют минимальную общую длину^[1].

Краткое описание алгоритма Править

Алгоритм предложил Джон Суурбалле и опубликовал в 1974 году^[2]. Основная идея алгоритма Суурбалле — использование алгоритма Дейкстры для поиска пути, модификация весов рёбер графа и затем прогон алгоритма Дейкстры второй раз. Выход алгоритма формируется путём комбинирования двух путей, отбрасывания рёбер, которые проходятся в противоположных направлениях этими путями, и использования оставшихся рёбер для формирования путей, которые и служат выходом алгоритма.

Модификация весов подобна модификации весов в алгоритме Джонсона и сохраняет неотрицательность весов, позволяя второму экземпляру алгоритма Дейкстры найти правильный второй путь.

Задачу поиска двух непересекающихся путей с минимальным весом можно рассматривать как частный случай задачи потока минимальной стоимости, где имеется «поток» величиной два с единичной «пропускной способностью» каждого ребра. Алгоритм Суурбалле можно также рассматривать как частный случай алгоритма поиска потока минимальной стоимости, который повторно пропускает максимально возможный поток через кратчайший путь.

Первый найденный алгоритмом Суурбалле путь является кратчайшим путём для начального (нулевого) потока, а второй найденный алгоритмом Суурбалле путь является кратчайшим путём для остаточного графа после пропускания единичного потока через первый путь.

Определения Править

Пусть $\text{[math]}$ G будет взвешенным ориентированным графом с набором вершин $\text{[math]}$ V и набором рёбер $\text{[math]}$ E (рисунок A). Пусть $\text{[math]}$ s будет источником в $\text{[math]}$ G, и пусть $\text{[math]}$ t будет стоком. Пусть каждое ребро $\text{[math]}$ (u,v) в $\text{[math]}$ E из вершины $\text{[math]}$ u в вершину $\text{[math]}$ v имеет неотрицательную цену $\text{[math]}$ w(u,v).

Определим $\text{[math]}$ d(s,u) как цену кратчайшего пути к вершине $\text{[math]}$ u из вершины $\text{[math]}$ s в дереве кратчайших путей с корнем в $\text{[math]}$ s (рисунок C).

Замечание: Узел и Вершина часто употребляются как синонимы.

Алгоритм Править

Алгоритм Суурбалле выполняет следующие шаги:

Ищется дерево кратчайших путей $\text{[math]}$ T с корнем в узле $\text{[math]}$ s путём прогона алгоритма Дейкстры (рисунок C). Это дерево содержит для любой вершины $\text{[math]}$ u кратчайший путь из $\text{[math]}$ s в $\text{[math]}$ u. Пусть $\text{[math]}$ P₁ будет наименьшим по стоимости путём из $\text{[math]}$ s в $\text{[math]}$ t (рисунок B). Рёбра дерева $\text{[math]}$ T называются рёбрами дерева, а остальные рёбра (рёбра, отсутствующие на рисунке C), называются рёбрами вне дерева.
Модифицируем стоимость каждого ребра графа, заменяя цену $\text{[math]}$ w(u,v) каждого ребра $\text{[math]}$ (u,v) на $\text{[math]}$ $\text{[math]}$ $w'(u,v)=w(u,v)-d(s,v)+d(s,u)$ . Согласно функции модификации цены все рёбра дерева будут иметь стоимость 0, а рёбра вне дерева будут иметь неотрицательные цены. Например,
если $\text{[math]}$ $\text{[math]}$ $u=B,v=E$ , то $\text{[math]}$ $\text{[math]}$ $w'(u,v)=w(B,E)-d(A,E)+d(A,B)=2-3+1=0$
если $\text{[math]}$ $\text{[math]}$ $u=E,v=B$ , то $\text{[math]}$ $\text{[math]}$ $w'(u,v)=w(E,B)-d(A,B)+d(A,E)=2-1+3=4$
Создаём остаточный граф $\text{[math]}$ G_t, образованный из $\text{[math]}$ G путём удаления рёбер $\text{[math]}$ G по пути $\text{[math]}$ P₁, которые направлены в $\text{[math]}$ s, а затем обращаются направления рёбер с нулевой длиной вдоль пути $\text{[math]}$ $\text{[math]}$ $P_{1}$ (рисунок D).
Находится кратчайший путь $\text{[math]}$ $\text{[math]}$ $P_{2}$ в остаточном графе $\text{[math]}$ $\text{[math]}$ $G_{t}$ путём прогона алгоритма Дейкстры (рисунок E).
Отбрасываем обратные рёбра пути $\text{[math]}$ P₂ из обоих путей. Оставшиеся рёбра путей $\text{[math]}$ P₁ и $\text{[math]}$ P₂ образуют из подграфа с двумя исходящими рёбрами из $\text{[math]}$ s, двумя входящими рёбрами $\text{[math]}$ t, и по одному входящему и одному исходящему ребру в каждой оставшейся вершине. Поэтому этот подграф состоит из двух не имеющих общих рёбер путей из $\text{[math]}$ s в $\text{[math]}$ t и, возможно, некоторых дополнительных циклов (нулевой длины). Алгоритм возвращает два непересекающихся (по рёбрам) пути из подграфа.

Пример Править

Следующий пример показывает, как алгоритм Суурбалле находит кратчайшую пару непересекающихся путей из A в F.

Рисунок A показывает взвешенный граф G.

Рисунок B вычисляет кратчайший путь P₁ из A в F (A-B-D-F).

Рисунок C показывает дерево кратчайших путей T с корнем в A и вычисленные расстояния из A в любую вершину ( $\text{[math]}$ u).

Рисунок D показывает остаточный граф G_t с обновлёнными ценами каждого ребра и рёбра пути P₁ обращены.

Рисунок E вычисляет путь P₂ в остаточном графе G_t (A-C-D-B-E-F).

Рисунок F показывает оба пути P₁ и P₂.

Рисунок G находит кратчайшую пару непересекающихся (по рёбрам) путей путём комбинации рёбер путей P₁ и P₂ и отбрасыванием общих взаимно противоположных дуг между обоими путями (B-D). Как результат, мы получаем кратчайшую пару непересекающихся путей (A-B-E-F) и (A-C-D-F).

Корректность Править

Вес любого пути из $\text{[math]}$ s в $\text{[math]}$ t в модифицированной системе весов равен весу в исходном графе, минус $\text{[math]}$ d(s,t). Поэтому два кратчайших непересекающихся пути после модификации весов будут теми же самыми двумя кратчайшими путями в исходном графе, хотя вес будет другой.

Алгоритм Суурбалле можно рассматривать как специальный случай применения методов кратчайшего пути для нахождения потока минимальной стоимости с общим потоком два из $\text{[math]}$ s в $\text{[math]}$ t. Модификация весов не влияет на найденные алгоритмом пути, только на их вес. Таким образом, корректность алгоритма следует из корректности метода поиска кратчайшего пути.

Анализ и время работы Править

Этот алгоритм требует двух итераций алгоритма Дейкстры. При использовании фибоначчиевых куч обе итерации могут быть выполнены за время $\text{[math]}$ $\text{[math]}$ $O(|E|+|V|\log |V|)$ , где $\text{[math]}$ $\text{[math]}$ $|V|$ и $\text{[math]}$ $\text{[math]}$ $|E|$ являются числом вершин и рёбер соответственно. Таким образом, те же самые границы приложимы и к алгоритму Суурбалле.

Вариации Править

Версия алгоритма Суурбалле, как описано выше, находит пути, не имеющие общих рёбер, но, возможно, имеющие общие вершины. Можно использовать тот же алгоритм для нахождения путей, не имеющих общих вершин, путём замены каждой вершины парой смежных вершин, одна со всеми входящими дугами $\text{[math]}$ u-in исходной вершины, другая со всеми исходящими дугами $\text{[math]}$ u-out. Два пути без общих дуг в этом модифицированном графе обязательно соответствует двум путям без общих вершин в исходном графе и наоборот, так что применение алгоритма Суурбалле к модифицированному графу приводит к построению двух путей без общих вершин в исходном графе. Исходный алгоритм Суурбалле 1974 года был версией с путями без общих вершин и его расширили в 1984 году Суурбалле и Тарьян на версию с путями без общих рёбер^[3].

При использовании модифицированной версии алгоритма Дейкстры, который одновременно вычисляет расстояния до каждой вершины $\text{[math]}$ t в графах $\text{[math]}$ G_t, также можно найти полные длины кратчайших путей из заданной вершины $\text{[math]}$ s в любую другую вершину графа за время, пропорциональное работе одного прогона алгоритма Дейкстры.

Замечание: Пара смежных вершин, полученная разбиением вершины, связана ориентированной дугой с нулевой ценой из вершины со входящими дугами в вершину с исходящими дугами. Источником становится $\text{[math]}$ s-out, а стоком становится $\text{[math]}$ t-in.

Примечания Править

↑ Bhandari, 1999, с. 86–91.
↑ Suurballe, 1974, с. 125–145.
↑ Suurballe, Tarjan, 1984, с. 325–336.

Литература Править

Ramesh Bhandari. Suurballe's disjoint pair algorithms // Survivable Networks: Algorithms for Diverse Routing. — Springer-Verlag, 1999. — С. 86–91. — ISBN 978-0-7923-8381-9.
Suurballe J. W. Disjoint paths in a network. — 1974. — Т. 4. — С. 125–145. — doi:10.1002/net.3230040204.
Suurballe J. W., Tarjan R. E. quick method for finding shortest pairs of disjoint paths. — 1984. — Т. 14. — С. 325–336. — doi:10.1002/net.3230140209.

[_4ce94e1df8afd4cb-1] Bhandari, 1999, с. 86–91.

[_395e23537eb8ed0e-2] Suurballe, 1974, с. 125–145.

[_73cffe6957b9fa43-3] Suurballe, Tarjan, 1984, с. 325–336.

[1]

[2]

[3]