Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Edge disjoint shortest pair algorithm
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.