**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Edge disjoint shortest pair algorithm

Summary

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. For an undirected graph G(V, E), it is stated 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 destination vertex now. The desired pair of paths results.
In lieu of the general purpose Ford's shortest path algorithm valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari provides two different algorithms, either one of which can be used in Step 4. One algorithm is a slight modification of the traditional Dijkstra's algorithm, and the other called the Breadth-First-Search (BFS) algorithm is a variant of the Moore's algorithm. Because the negative arcs are only on the first shortest path, no negative cycle arises in the transformed graph (Steps 2 and 3). In a nonnegative graph, the modified Dijkstra algorithm reduces to the traditional Dijkstra's algorithm, and can therefore be used in Step 1 of the above algorithm (and similarly, the BFS algorithm).
G = (V, E)
d(i) – the distance of vertex i (i∈V) from source vertex A; it is 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.
Assign S = V-{A}, where V is the set of vertices in the given graph.
Assign P(i) = A, ∀i∈S.

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.