- Edge disjoint shortest pair algorithm
Edge disjoint shortest pair algorithm is an
algorithm incomputer network routing for generating the shortest pair of edge disjoint paths between a given pair of vertices 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.G = (V, E)d(i) – the distance of vertex i (i∈V) from source vertex A; it’s the sum of arcs in a possiblepath 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); ΓA ≡ 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)
Wikimedia Foundation. 2010.
Edge disjoint shortest pair algorithm
Look at other dictionaries:
Kruskal's algorithm — is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is… … Wikipedia
Routing — This article is about routing in networks. For other uses, see Routing (disambiguation). 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… … Wikipedia
Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… … Wikipedia
Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Distance-hereditary graph — A distance hereditary graph. In graph theoretic mathematics, a distance hereditary graph (also called a completely separable graph)[1] is a graph in which the distances in any connected induced subgraph are the same as they are in the original… … Wikipedia
Algorithmics of sudoku — The class of Sudoku puzzles consists of a partially completed row column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N }), so … Wikipedia
Induced path — An induced path of length four in a cube. Finding the longest induced path in a hypercube is known as the snake in the box problem. In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced… … Wikipedia
