This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Edge disjoint shortest pair algorithm" – news · newspapers · books · scholar · JSTOR(January 2010) (Learn how and when to remove this message)
Edge disjoint shortest pair algorithm is an algorithm in computer network routing.[1] 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[2][3] valid for negative arcs present anywhere in a graph (with nonexistent negative cycles), Bhandari[4] 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.[5][6] 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).
^Bhandari, Ramesh (1999). Survivable networks: algorithms for diverse routing. Springer. p. 46. ISBN 0-7923-8381-8.
^Ford, L. R. (1956). Network Flow Theory, Report P-923. Santa Monica, California: Rand Corporation.
^Jones, R. H.; Steele, N. C. (1989). Mathematics in Communication Theory. Chichester: Ellis Harwood (division of John Wiley & Sons). p. 74. ISBN 0-470-21246-2.
^Bhandari, Ramesh (1999). Survivable Networks: Algorithms for Diverse Routing. Springer. pp. 21–37. ISBN 0-7923-8381-8.
^E. F. Moore (1959) "The Shortest Path through the Maze", Proceedings of the International Symposium on the Theory of Switching, Part II, Harvard University Press, p. 285-292
^Kershenbaum, Aaron (1993). Telecommunications Network Design Algorithms. McGraw-Hill. pp. 159–162. ISBN 0-07-034228-8.
and 22 Related for: Edge disjoint shortest pair algorithm information
Edgedisjointshortestpairalgorithm is an algorithm in computer network routing. The algorithm is used for generating the shortestpair of edge disjoint...
Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 549–552, ISBN 0-262-03293-7 Tarjan, Robert E. (1976), "Edge-disjoint spanning trees...
non-negative edge weights Floyd–Warshall algorithm: solves the all pairsshortest path problem in a weighted, directed graph Johnson's algorithm: all pairs shortest...
single connected component. An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph...
the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the push-relabel algorithm of...
question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns...
is a graph spanner constructed by a greedy algorithm, generally one that considers all edges from shortest to longest and keeps the ones that are needed...
its edges for the shortest red–blue edge. Conversely, for any red–blue coloring of any subset of a given set of points, the bichromatic closest pair produces...
the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is...
{and}}\;x\neq y\}} , a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with two distinct...
most 4.7998 {\displaystyle 4.7998} . Several published algorithms claiming to find the shortest opaque set for a convex polygon were later shown to be...
denote the number of edges between S and T. If the two sets are not disjoint, edges in their intersection are counted twice, that is, E ( S , T ) = 2 |...
just one edge of the spanning tree, the vertices are partitioned into two disjoint sets. The fundamental cutset is defined as the set of edges that must...
answer is "no" (also known as a semi-algorithm). This algorithm is enormously impractical, even if P = NP. If the shortest program that can solve SUBSET-SUM...
decomposition involving disjoint union and complement graph operations that can be represented concisely by a labeled tree, and used algorithmically to efficiently...
for the single source shortest path algorithm in planar graphs for nonnegative edge-lengths and proposed a linear time algorithm. Their method generalizes...
already lie close together, therefore every suitable shortest-path algorithm such as Dijkstra's algorithm or extensions thereof can be chosen. The pre-computed...
and w there is a unique median vertex m(u,v,w) that lies on shortest paths between each pair of the three vertices. As with median graphs more generally...
components diameter, the longest of the shortest path lengths between pairs of vertices girth, the length of the shortest cycle Vertex connectivity, the smallest...
Global Information