Edge disjoint shortest pair algorithm
Encyclopedia
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.
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);
Γi ≡ 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)
b) S = S ∪{i}
Go to Step 2.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
in computer network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
routing
Routing
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
. The algorithm is used for generating the shortest pair of edge disjoint paths between a given pair of vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
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.
Suurballe's algorithm
Suurballe's algorithm
In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed graph, so that both paths connect the same pair of vertices and have minimum total length. The algorithm was conceived by J. W. Suurballe...
solves the same problem more quickly by reweighting the edges of the graph to avoid negative costs, allowing Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
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;
= ∞, otherwise (∞ is a large number defined below);
Γi ≡ 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)
b) S = S ∪{i}
Go to Step 2.