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:
“screenwriter
Listen, little Elia: draw your chair up close to the edge of the precipice and I’ll tell you a story.”
—F. Scott Fitzgerald (1896–1940)
“The Gettysburg speech is at once the shortest and the most famous oration in American history. Put beside it, all the whoopings of the Websters, Sumners and Everetts seem gaudy and silly. It is eloquence brought to a pellucid and almost gem-like perfection—the highest emotion reduced to a few poetical phrases.”
—H.L. (Henry Lewis)
“I well recall my horror when I heard for the first time, of a journalist who had laid in a pair of what were then called bicycle pants and taken to golf; it was as if I had encountered a studhorse with his hair done up in frizzes, and pink bowknots peeking out of them. It seemed, in some vague way, ignominious, and even a bit indelicate.”
—H.L. (Henry Lewis)