Русская Википедия:Алгоритм Суурбалле
Алгоритм Суурбалле — это алгоритм нахождения двух непересекающихся (не имеющих общих рёбер) путей в ориентированном графе с неотрицательными весами, так что оба пути связывают ту же самую пару вершин и имеют минимальную общую длинуШаблон:Sfn.
Краткое описание алгоритма
Алгоритм предложил Джон Суурбалле и опубликовал в 1974 годуШаблон:Sfn. Основная идея алгоритма Суурбалле — использование алгоритма Дейкстры для поиска пути, модификация весов рёбер графа и затем прогон алгоритма Дейкстры второй раз. Выход алгоритма формируется путём комбинирования двух путей, отбрасывания рёбер, которые проходятся в противоположных направлениях этими путями, и использования оставшихся рёбер для формирования путей, которые и служат выходом алгоритма.
Модификация весов подобна модификации весов в алгоритме Джонсона и сохраняет неотрицательность весов, позволяя второму экземпляру алгоритма Дейкстры найти правильный второй путь.
Задачу поиска двух непересекающихся путей с минимальным весом можно рассматривать как частный случай задачи потока минимальной стоимости, где имеется «поток» величиной два с единичной «пропускной способностью» каждого ребра. Алгоритм Суурбалле можно также рассматривать как частный случай алгоритма поиска потока минимальной стоимости, который повторно пропускает максимально возможный поток через кратчайший путь.
Первый найденный алгоритмом Суурбалле путь является кратчайшим путём для начального (нулевого) потока, а второй найденный алгоритмом Суурбалле путь является кратчайшим путём для остаточного графа после пропускания единичного потока через первый путь.
Определения
Пусть Шаблон:Math будет взвешенным ориентированным графом с набором вершин Шаблон:Math и набором рёбер Шаблон:Math (рисунок A). Пусть Шаблон:Math будет источником в Шаблон:Math, и пусть Шаблон:Math будет стоком. Пусть каждое ребро Шаблон:Math в Шаблон:Math из вершины Шаблон:Math в вершину Шаблон:Math имеет неотрицательную цену Шаблон:Math.
Определим Шаблон:Math как цену кратчайшего пути к вершине Шаблон:Math из вершины Шаблон:Math в дереве кратчайших путей с корнем в Шаблон:Math (рисунок C).
Замечание: Узел и Вершина часто употребляются как синонимы.
Алгоритм
Алгоритм Суурбалле выполняет следующие шаги:
- Ищется дерево кратчайших путей Шаблон:Math с корнем в узле Шаблон:Math путём прогона алгоритма Дейкстры (рисунок C). Это дерево содержит для любой вершины Шаблон:Math кратчайший путь из Шаблон:Math в Шаблон:Math. Пусть Шаблон:Math будет наименьшим по стоимости путём из Шаблон:Math в Шаблон:Math (рисунок B). Рёбра дерева Шаблон:Math называются рёбрами дерева, а остальные рёбра (рёбра, отсутствующие на рисунке C), называются рёбрами вне дерева.
- Модифицируем стоимость каждого ребра графа, заменяя цену Шаблон:Math каждого ребра Шаблон:Math на <math>w' (u,v) = w(u,v) - d(s,v) + d(s,u)</math>. Согласно функции модификации цены все рёбра дерева будут иметь стоимость 0, а рёбра вне дерева будут иметь неотрицательные цены. Например,
если <math>u=B, v=E</math>, то <math>w'(u,v) = w(B,E) - d(A,E) + d(A,B) = 2 - 3 + 1 = 0</math>
если <math>u=E, v=B</math>, то <math>w'(u,v) = w(E,B) - d(A,B) + d(A,E) = 2 - 1 + 3 = 4</math> - Создаём остаточный граф Шаблон:Math, образованный из Шаблон:Math путём удаления рёбер Шаблон:Math по пути Шаблон:Math, которые направлены в Шаблон:Math, а затем обращаются направления рёбер с нулевой длиной вдоль пути <math>P_1</math> (рисунок D).
- Находится кратчайший путь <math>P_2</math> в остаточном графе <math>G_t</math> путём прогона алгоритма Дейкстры (рисунок E).
- Отбрасываем обратные рёбра пути Шаблон:Math из обоих путей. Оставшиеся рёбра путей Шаблон:Math и Шаблон:Math образуют из подграфа с двумя исходящими рёбрами из Шаблон:Math, двумя входящими рёбрами Шаблон:Math, и по одному входящему и одному исходящему ребру в каждой оставшейся вершине. Поэтому этот подграф состоит из двух не имеющих общих рёбер путей из Шаблон:Math в Шаблон:Math и, возможно, некоторых дополнительных циклов (нулевой длины). Алгоритм возвращает два непересекающихся (по рёбрам) пути из подграфа.
Пример
Следующий пример показывает, как алгоритм Суурбалле находит кратчайшую пару непересекающихся путей из A в F.
Рисунок A показывает взвешенный граф G.
Рисунок B вычисляет кратчайший путь P1 из A в F (A-B-D-F).
Рисунок C показывает дерево кратчайших путей T с корнем в A и вычисленные расстояния из A в любую вершину (Шаблон:Math).
Рисунок D показывает остаточный граф Gt с обновлёнными ценами каждого ребра и рёбра пути P1 обращены.
Рисунок E вычисляет путь P2 в остаточном графе Gt (A-C-D-B-E-F).
Рисунок F показывает оба пути P1 и P2.
Рисунок G находит кратчайшую пару непересекающихся (по рёбрам) путей путём комбинации рёбер путей P1 и P2 и отбрасыванием общих взаимно противоположных дуг между обоими путями (B-D). Как результат, мы получаем кратчайшую пару непересекающихся путей (A-B-E-F) и (A-C-D-F).
Корректность
Вес любого пути из Шаблон:Mvar в Шаблон:Mvar в модифицированной системе весов равен весу в исходном графе, минус Шаблон:Math. Поэтому два кратчайших непересекающихся пути после модификации весов будут теми же самыми двумя кратчайшими путями в исходном графе, хотя вес будет другой.
Алгоритм Суурбалле можно рассматривать как специальный случай применения методов кратчайшего пути для нахождения потока минимальной стоимости с общим потоком два из Шаблон:Mvar в Шаблон:Mvar. Модификация весов не влияет на найденные алгоритмом пути, только на их вес. Таким образом, корректность алгоритма следует из корректности метода поиска кратчайшего пути.
Анализ и время работы
Этот алгоритм требует двух итераций алгоритма Дейкстры. При использовании фибоначчиевых куч обе итерации могут быть выполнены за время <math>O(|E| + |V|\log |V|)</math>, где <math>|V|</math> и <math>|E|</math> являются числом вершин и рёбер соответственно. Таким образом, те же самые границы приложимы и к алгоритму Суурбалле.
Вариации
Версия алгоритма Суурбалле, как описано выше, находит пути, не имеющие общих рёбер, но, возможно, имеющие общие вершины. Можно использовать тот же алгоритм для нахождения путей, не имеющих общих вершин, путём замены каждой вершины парой смежных вершин, одна со всеми входящими дугами Шаблон:Math исходной вершины, другая со всеми исходящими дугами Шаблон:Math. Два пути без общих дуг в этом модифицированном графе обязательно соответствует двум путям без общих вершин в исходном графе и наоборот, так что применение алгоритма Суурбалле к модифицированному графу приводит к построению двух путей без общих вершин в исходном графе. Исходный алгоритм Суурбалле 1974 года был версией с путями без общих вершин и его расширили в 1984 году Суурбалле и Тарьян на версию с путями без общих рёберШаблон:Sfn.
При использовании модифицированной версии алгоритма Дейкстры, который одновременно вычисляет расстояния до каждой вершины Шаблон:Math в графах Шаблон:Math, также можно найти полные длины кратчайших путей из заданной вершины Шаблон:Math в любую другую вершину графа за время, пропорциональное работе одного прогона алгоритма Дейкстры.
Замечание: Пара смежных вершин, полученная разбиением вершины, связана ориентированной дугой с нулевой ценой из вершины со входящими дугами в вершину с исходящими дугами. Источником становится Шаблон:Math, а стоком становится Шаблон:Math.
Примечания
Литература
