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

Алгоритм кратчайшей пары непересекающихся ребер это алгоритм маршрутизации компьютерных сетей — . Алгоритм используется для генерации кратчайшей пары непересекающихся путей между заданной парой вершин . Для неориентированного графа G(V, E) это формулируется следующим образом:

1. Запустите алгоритм поиска кратчайшего пути для данной пары вершин.
2. Замените каждое ребро кратчайшего пути (эквивалентного двум противоположно направленным дугам) одной дугой, направленной к исходной вершине.
3. Сделайте длину каждой из вышеуказанных дуг отрицательной.
4. Запустите алгоритм кратчайшего пути (Примечание: алгоритм должен принимать отрицательные затраты)
5. Сотрите перекрывающиеся края двух найденных путей и измените направление оставшихся дуг на первом кратчайшем пути так, чтобы каждая дуга на нем теперь была направлена ​​к целевой вершине. В результате получается желаемая пара путей.

Вместо общего алгоритма поиска кратчайшего пути Форда. действительно для отрицательных дуг, присутствующих в любом месте графа (с несуществующими отрицательными циклами), Бхандари предоставляет два разных алгоритма, каждый из которых можно использовать на шаге 4. Один алгоритм представляет собой небольшую модификацию традиционного алгоритма Дейкстры , а другой, называемый алгоритмом поиска в ширину (BFS), является вариантом алгоритма Мура. Поскольку отрицательные дуги находятся только на первом кратчайшем пути, в преобразованном графе не возникает отрицательного цикла (шаги 2 и 3). В неотрицательном графе модифицированный алгоритм Дейкстры сводится к традиционному алгоритму Дейкстры и, следовательно, может использоваться на этапе 1 приведенного выше алгоритма (и, аналогично, алгоритма BFS).

Модифицированный алгоритм Дейкстры

Источник:

Г = (В, Е) d(i) – расстояние вершины i (iεV) от исходной вершины A; это сумма дуг возможных путь от вершины A до вершины i. Обратите внимание, что d(A)=0; P(i) – предшественник вершины i на том же пути. Z – вершина назначения

Шаг 1.

Start with d(A) = 0,
d(i)     = l (Ai), if i∈ΓA;  Γi ≡ set of neighbor vertices of vertex i, l(ij) = length of arc from vertex i to vertex j.
      
         = ∞, otherwise.       
Assign S = V-{A}, where V is the set of vertices in the given graph.
Assign P(i) = A, ∀i∈S.

Шаг 2.

a) Find j∈S such that d(j) = min d(i), i∈S.
b) Set S = S – {j}.
c) If j = Z (the destination vertex), END; otherwise go to Step 3.

Шаг 3.

∀i∈Γj, if d(j) + l(ji) < d(i),
a) set d(i) = d(j) + l(ji), P(i) = j.
b) S = S ∪{i}
Go to Step 2.

Пример

Основные этапы алгоритма кратчайшей пары с непересекающимися ребрами показаны ниже:

Graphical Illustration of the Shortest Pair of Disjoint Paths Algorithm

На рисунке A показан заданный неориентированный граф G(V, E) с весами ребер.

На рисунке B показан рассчитанный кратчайший путь ABCZ от A до Z (жирными линиями).

На рисунке C показано обращение дуг кратчайшего пути и их отрицательные веса.

На рисунке D показан кратчайший путь ADCBZ от A до Z, определенный в новом преобразовании. граф на рисунке C (это определяется с помощью модифицированного алгоритма Дейкстры (или алгоритма BFS), действующего для таких отрицательных дуг; в таком преобразованном графе никогда не бывает отрицательных циклов).

На рисунке E показан определенный кратчайший путь ADCBZ на исходном графике.

На рисунке F показана определенная кратчайшая пара непересекающихся путей (ABZ, ADCZ), найденная после стирания ребра BC, общего для путей ABCZ и ADCBZ, и соответствующей группировки оставшихся ребер.

Обсуждение

В неотрицательном графе модифицированный алгоритм Дейкстры функционирует как традиционный алгоритм Дейкстры. В графе, характеризующемся вершинами со степенью O(d) (d<|V|), эффективность равна O(d|V|), то есть O(|V| ² ), в худшем случае, как в традиционном случае Дейкстры.

В преобразованном графе алгоритма кратчайшей пары непересекающихся ребер, который содержит отрицательные дуги, данная вершина, ранее «постоянно» помеченная на этапе 2a модифицированного алгоритма Дейкстры, может быть повторно посещена и перемаркирована на этапе 3a и вставлена ​​обратно в набор вершин S ( Шаг 3б). Эффективность модифицированного Дейкстры в таком преобразованном графе становится O(d ² |V|), являющийся O(|V| ³ ) в худшем случае. Большинство графов, представляющих практический интерес, обычно разрежены и имеют степени вершин O(1), и в этом случае эффективность модифицированного алгоритма Дейкстры, примененного к преобразованному графу, становится O(|V|) (или, что то же самое, O(|E| )). Алгоритм кратчайшей пары, не пересекающийся по ребрам, тогда становится сравнимым по эффективности с алгоритмом Суурбалля , который в общем имеет значение O(|V| ² ) из-за дополнительного преобразования графа, которое изменяет вес графа, чтобы избежать дуг с отрицательной стоимостью, что позволяет алгоритм Дейкстры использовать для обоих шагов кратчайшего пути. Повторное взвешивание требует построения всего дерева кратчайших путей с корнем в исходной вершине. Обходя это дополнительное преобразование графа и используя вместо него модифицированный алгоритм Дейкстры, подход Бхандари приводит к упрощенной версии алгоритма кратчайшей пары непересекающихся ребер без особого ущерба для эффективности, по крайней мере, для разреженных графов. Получившаяся простая форма в дальнейшем поддается легкому расширению. к алгоритмам K (>2) непересекающихся путей и их вариациям, таким как частично непересекающиеся пути, когда полной непересекаемости не существует, а также к графам с ограничениями, с которыми сталкивается практикующий сетевой специалист в более сложных реальных сетях.

Вершинно-непересекающаяся версия описанного выше алгоритма кратчайшей пары путей, не пересекающихся по ребрам, получается путем разделения каждой вершины (за исключением вершин источника и назначения) первого кратчайшего пути на шаге 3 алгоритма, соединяя разделенную пару вершин нулевым весовая дуга (направленная к исходной вершине) и замена любого инцидентного ребра двумя противоположно направленными дугами, одна инцидентная в вершине расщепляемой пары (ближе к исходной вершине), а другая дуга, исходящая из другой вершины. Варианты K (>2) получаются аналогично, например, вершины кратчайшего ребра непересекающейся пары путей (за исключением вершин источника и назначения) разбиваются, при этом вершины в каждой расщепленной паре соединяются друг с другом дугами с нулевым значением. вес, а также внешние края аналогичным образом ^[8][9] . Алгоритмы, представленные для неориентированных графов, также распространяются на ориентированные графы и в целом применимы к любой задаче (в любой технической дисциплине), которую можно смоделировать как граф вершин и ребер (или дуг).