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:
- 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 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.
Read more about Edge Disjoint Shortest Pair Algorithm: Algorithm
Famous quotes containing the words edge, shortest and/or pair:
“They call back to us
from the gauzy edge of paradise,
good news, good news.”
—Anne Sexton (1928–1974)
“The shortest route is not the most direct one, but rather the one where the most favorable winds swell our sails:Mthat is the lesson that seafarers teach. Not to abide by this lesson is to be obstinate: here, firmness of character is tainted with stupidity.”
—Friedrich Nietzsche (1844–1900)
“I should have been a pair of ragged claws
Scuttling across the floors of silent seas.”
—T.S. (Thomas Stearns)