Shortest two disjoint paths between two specified vertices

5
votes

Given a weighted undirected graph G and two vertices a, b, we want to find two paths a -> b and b -> a such that they don't share any edge, and such that the sum of weights of edges in both paths is minimum. There can be up to 1,000 vertices, and up to 10,000 edges.

I had initially tried to come up with a dynamic programming approach, but couldn't find such. Any ideas/suggestions would be extremely appreciated.

1
algorithmoptimizationgraph-theorydynamic-programming
Can weights be negative? - 6502
If I have understood you question correctly. Then first check whether there exists two different paths for given pair of vertices which wont share any edge. If it exist then while walking from source to destination using dynamic programming and note all the edges and remove those edges from original graph G=(v,E) which reduces to G'(V,E') .Then while coming since graph G' is reduced try applying the dynamic programming to reach from destination to source... - Imposter
@6502 No, weights can't be negative. - Chris
@Imposter: that doesn't work. As a counter-example see raksy.dyndns.org/graph.png where there are two distinct paths (A345B and B12A) however if you start from A looking for a minimal path you end up with A12B and then there is no way for coming back. - 6502
@6502: He said the graph is undirected. That said, I think what he's trying to say doesn't work due to Evgeny's counter-example below (though I don't understand where dynamic programming comes into it...) - BlueRaja - Danny Pflughoeft

1 Answers

7
votes

This is Minimum-cost flow problem. You can assign flow capacity for each edge equal to 1, then search for a minimum-cost flow between a and b with flow=2.

Someone may think that it is possible to use a simple algorithm to find shortest path from a to b, remove its edges from the graph, then find another shortest path.

This approach is not always optimal. For some graphs it gives a good approximation. For others it may give a very bad solution:

enter image description here

Here after removing edges of the first shortest path (green), the only remaining path (red) is very heavy. The cost of this solution is 1+1+10+1+1+2+90+2=108. While optimal cost is 1+15+1+2+1+10+1+2=32.