Edge disjoint shortest pair algorithm

Updated on Oct 18, 2023

Edit

Comment

Edge disjoint shortest pair algorithm is an algorithm in computer network routing. The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of vertices as follows:

Run the shortest path algorithm for the given pair of vertices

Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex

Make the length of each of the above arcs negative

Run the shortest path algorithm (Note: the algorithm should accept negative costs)

Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the sink vertex now. The desired pair of paths results.

Suurballe's algorithm solves the same problem more quickly by reweighting the edges of the graph to avoid negative costs, allowing Dijkstra's algorithm to be used for both shortest path steps.

Algorithm

G = (V, E) d(i) – the distance of vertex i (i∈V) from source vertex A; it’s the sum of arcs in a possible path from vertex A to vertex i. Note that d(A)=0; P(i) – the predecessor of vertex I on the same path. Z – the destination vertex

Step 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 (∞ is a large number defined below); Assign S = V-{A}, where V is the set of vertices in the given graph. Assign P(i) = A, ∀i∈S.

Step 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.

Step 3.

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

References

Edge disjoint shortest pair algorithm Wikipedia

(Text) CC BY-SA