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:

  • 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
  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. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.