Edge disjoint shortest pair algorithm

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

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

  1. Bhandari, Ramesh (1999). Survivable networks: algorithms for diverse routing 477. Springer. p. 46. ISBN 0-7923-8381-8.


This article is issued from Wikipedia - version of the Wednesday, October 08, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.