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:
“Americans see history as a straight line and themselves standing at the cutting edge of it as representatives for all mankind. They believe in the future as if it were a religion; they believe that there is nothing they cannot accomplish, that solutions wait somewhere for all problems, like brides.”
—Frances Fitzgerald (b. 1940)
“The shortest answer is doing.”
—English proverb, collected in George Herbert, Jacula Prudentum (1651)
“Here comes a pair of very strange beasts, which in all
tongues are called fools.”
—William Shakespeare (1564–1616)