Shortest two disjoint paths between two specified

问题:

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:

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:

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.