Реберный непересекающийся алгоритм кратчайшей пары - Edge disjoint shortest pair algorithm

Реберный непересекающийся алгоритм кратчайшей пары является алгоритм в компьютерная сеть маршрутизация.^[1] Алгоритм используется для генерации кратчайшей пары непересекающихся путей между заданной парой вершины следующее:

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

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

Алгоритм

G = (V, E) d (i) - расстояние между вершиной i (i∈V) от исходной вершины A; это сумма дуг возможного пути от вершины A к вершине i. Обратите внимание, что d (A) = 0; P (i) - предшественник вершины I на том же пути. Z - вершина назначения

Шаг 1.

Начнем с d (A) = 0, d (i) = l (Ai), если i∈ΓA; Γi ≡ множество соседних вершин вершины i, l (ij) = длина дуги от вершины i до вершины j. = ∞, иначе (∞ - большое число, определенное ниже); Положим S = V- {A}, где V - множество вершин данного графа. Положим P (i) = A, ∀i∈S.

Шаг 2.

a) Найдите j∈S такое, что d (j) = min d (i), i∈S. b) Положите S = S - {j}. c) Если j = Z (конечная вершина), END; в противном случае переходите к шагу 3.

Шаг 3.

∀i∈Γj, если d (j) + l (ij) 
Рекомендации









 Бхандари, Рамеш (1999). Живые сети: алгоритмы разнообразной маршрутизации. 477. Springer. п. 46. ISBN  0-7923-8381-8.