Edge disjoint shortest pair algorithm

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

• Run the shortest pair 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.

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;
                 = ∞, otherwise (∞ is a large number defined below);
               ΓA ≡ set of neighbor vertices of vertex i,
               l(ij) = length of arc from vertex i to vertex j.
        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.