Jump to content

Edge disjoint shortest pair algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Umreemala (talk | contribs) at 17:57, 19 September 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Edge Disjoint Shortest Pair Algorithm

The algorithm for generating a shortest pair of edge disjoint paths between a given pair of vertices is stated 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 the 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 paths such that each arc on it is directed towards the sink vertex now. The desired pair of paths results.

Proof of Concept

To be done

Retrieved from "https://en.wikipedia.org/w/index.php?title=Edge_disjoint_shortest_pair_algorithm&oldid=23535919"