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

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

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

Определения

Пусть $G$ — взвешенный ориентированный граф с множеством вершин $V$ и множеством ребер $E$ (рисунок A); пусть $s$ будет назначенной исходной вершиной в $G$ и пусть $t$ будет назначенной вершиной назначения. Пусть каждое ребро $(u, v)$ в $E$ , от вершины $u$ до вершины $v$ , имеет неотрицательную стоимость $w (u, v)$ .

Определим $d(s, u)$ как стоимость кратчайшего пути к вершине $u$ из вершины $s$ в дереве кратчайших путей с корнем в $s$ (рисунок C).

Примечание. Узел и вершина часто используются как взаимозаменяемые.

Алгоритм

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

Найдите дерево кратчайших путей $T$ с корнем в узле $s$ , запустив алгоритм Дейкстры (рис. C). Это дерево содержит для каждой вершины $u$ кратчайший путь из $s$ в $u$ . Пусть $P 1$ — кратчайший стоимостной путь от $s$ до $t$ (рис. B). Ребра в $T$ называются ребрами дерева , а оставшиеся ребра (ребра, отсутствующие на рисунке C) называются ребрами, не являющимися деревом .
Измените стоимость каждого ребра в графе, заменив стоимость $w (u, v)$ каждого ребра $(u, v)$ на $w ' (u, v) = w (u, v) - d(s, v) + d(s, ты)$ . Согласно полученной модифицированной функции стоимости, все ребра дерева имеют стоимость 0, а ребра, не являющиеся деревьями, имеют неотрицательную стоимость. Например:
Если $u =B, v =E$ , то $w' (u, v) = w (B,E) - d(A,E) + d(A,B) = 2 - 3 + 1 = 0$
Если $u =E, v =B$ , то $w' (u, v) = w (E,B) - d(A,B) + d(A,E) = 2 - 1 + 3 = 4$
Создайте остаточный граф $G t,$ сформированный из $G,$ удалив ребра $G$ на пути $P 1$ , которые направлены в $s$ , а затем поменяйте направление ребер нулевой длины на пути $P 1$ (рисунок D).
Найдите кратчайший путь $P 2$ в графе остатков $G t$ , запустив алгоритм Дейкстры (рисунок E).
Отбросьте перевернутые ребра $P 2$ из обоих путей. Оставшиеся ребра $P1, а также$ и $P2 одним$ образуют подграф с двумя исходящими ребрами в точке $s$ , двумя входящими ребрами в точке $t$ входящим и одним исходящим ребром в каждой оставшейся вершине. Следовательно, этот подграф состоит из двух непересекающихся по ребрам путей от $s$ до $t$ и, возможно, некоторых дополнительных циклов (нулевой длины). Верните два непересекающихся пути из подграфа.

Пример

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

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

На рисунке B вычислен кратчайший путь P ₁ от A до F ( A – B – D – F ).

Рисунок C иллюстрирует дерево кратчайших путей T с корнем в A и вычисленные расстояния от A до каждой вершины ( $u$ ).

На рисунке D показан остаточный граф G _t с обновленной стоимостью каждого ребра и перевернутыми ребрами пути P ₁ .

На рисунке E вычислен путь P ₂ в остаточном графе G _t ( A – C – D – B – E – F ).

Рисунок F путь P1 _P2 путь иллюстрирует _. и

Рисунок G находит кратчайшую пару непересекающихся путей путем объединения ребер путей P1 _B и P2 _и последующего отбрасывания общих перевернутых ребер между обоими путями ( – D ) . В результате мы получаем две кратчайшие пары непересекающихся путей ( A – B – E – F ) и ( A – C – D – F ).

Корректность

Вес любого пути от $s$ до $t$ в модифицированной системе весов равен весу в исходном графе минус $d(s, t)$ . Следовательно, два кратчайших непересекающихся пути с измененными весами — это те же самые пути, что и два кратчайших пути в исходном графе, хотя они имеют разные веса.

Алгоритм Суурбалле можно рассматривать как частный случай метода последовательных кратчайших путей для нахождения потока с минимальной стоимостью с общим объемом потока два от $s$ до $t$ . Модификация весов не влияет на последовательность путей, найденных этим методом, а только на их веса. Следовательно, корректность алгоритма следует из корректности метода последовательных кратчайших путей.

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

Этот алгоритм требует двух итераций алгоритма Дейкстры. Используя кучи Фибоначчи , обе итерации можно выполнить за время $O(|E|+|V|\log |V|)$ где $|V|$ и $|E|$ - количество вершин и ребер соответственно. Следовательно, та же временная граница применима и к алгоритму Суурбаля.

Вариации

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

Используя модифицированную версию алгоритма Дейкстры, который одновременно вычисляет расстояния до каждой вершины $t$ в графах $Gt,$ можно также найти общие длины кратчайших пар путей от заданной исходной вершины $s$ до каждой другой вершины в графе Gt. график за время, пропорциональное одному экземпляру алгоритма Дейкстры.

Примечание. Пара смежных вершин, возникшая в результате разделения, соединена однонаправленным ребром с нулевой стоимостью от входящей к исходящей вершине. Исходная вершина становится $s-out$ , а целевая вершина становится $t-in$ .

См. также

Алгоритм кратчайшей пары непересекающихся ребер

Ссылки

^ Бхандари, Рамеш (1999), «Алгоритмы непересекающихся пар Суурбалле», Survivable Networks: Algorithms for Diverse Routing , Springer-Verlag, стр. 86–91, ISBN 978-0-7923-8381-9 .
^ Суурбалле, JW (1974), «Непересекающиеся пути в сети», Networks , 4 (2): 125–145, doi : 10.1002/net.3230040204 .
^ Суурбалле, JW; Тарьян, Р.Э. (1984), «Быстрый метод поиска кратчайших пар непересекающихся путей» (PDF) , Networks , 14 (2): 325–336, doi : 10.1002/net.3230140209 .

[1] Бхандари, Рамеш (1999), «Алгоритмы непересекающихся пар Суурбалле», Survivable Networks: Algorithms for Diverse Routing , Springer-Verlag, стр. 86–91, ISBN 978-0-7923-8381-9 .

[2] Суурбалле, JW (1974), «Непересекающиеся пути в сети», Networks , 4 (2): 125–145, doi : 10.1002/net.3230040204 .

[3] Суурбалле, JW; Тарьян, Р.Э. (1984), «Быстрый метод поиска кратчайших пар непересекающихся путей» (PDF) , Networks , 14 (2): 325–336, doi : 10.1002/net.3230140209 .

[ 1 ]

[ 2 ]

[ 3 ]