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:
“It was her stern necessity: all things
Are of one pattern made; bird, beast, and flower,
Deceive us, seeming to be many things,
And are but one. Beheld far off, they differ
As God and devil; bring them to the mind,
They dull its edge with their monotony.”
—Ralph Waldo Emerson (1803–1882)
“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)
“Auld Noah was at hame wi’ them a’,
The lion and the lamb,
Pair by pair they entered the Ark
And he took them as they cam’.”
—Hugh MacDiarmid (1892–1978)