Calculating Divergent Paths on Subtending Rings

Question

I need to calculate two paths from A to B in the following graph, with the constraint that the paths can't share any edges:

hmm, okay, can't post images, here's a link.

All edges have positive weights; for this example I think we can assume that they're equal. My naive approach is to use Djikstra's algorithm to calculate the first path, shown in the second graph in the above image.

Then I remove the edges from the graph and try to calculate the second path, which fails. Is there a variation of Djikstra, Bellman-Ford (or anything else) that will calculate the paths shown in the third diagram above? (Without special knowledge and removal of the subtending link, is what I mean)

Answer 1

What you are looking for is edge-disjoint paths. Menger's Theorem will give you the maximum number of edge-disjoint paths. To find the shortest pair, take a look at the Edge disjoint shortest pair algorithm:

1. Run the shortest pair algorithm for the given pair of vertices
2. Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex
3. Make the length of each of the above arcs negative
4. Run the shortest path algorithm (Note: the algorithm should accept negative costs)
5. 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.