Edge disjoint shortest pair algorithm


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:
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 =
d – the distance of vertex i from source vertex A; it's the sum of arcs in a possible
path from vertex A to vertex i. Note that d=0;
P – the predecessor of vertex I on the same path.
Z – the destination vertex
Step 1.
Start with d = 0,
d = l, if i∈ΓA; Γi ≡ set of neighbor vertices of vertex i, l = length of arc from vertex i to vertex j.

= ∞, otherwise ;
Assign S = V-, where V is the set of vertices in the given graph.
Assign P = A, ∀i∈S.
Step 2.
a) Find j∈S such that d = min d, i∈S.
b) Set S = S –.
c) If j = Z, END; otherwise go to Step 3.
Step 3.
∀i∈Γj, if d + l < d,
a) set d = d + l, P = j.
b) S = S ∪
Go to Step 2.