The shortest two disjoint paths between two indicated vertices

Question

Given a weighted undirected graph G and two vertices a, b , we want to find two paths a → b and b → a , so that they do not share any edge, and therefore the sum of the weights of the edges in both paths is minimal. There can be up to 1000 peaks and up to 10,000 .

I initially tried to come up with a dynamic programming approach, but could not find one. Any ideas / suggestions would be greatly appreciated.

Answer 1

This is a problem with minimal costs . You can assign a throughput for each edge equal to 1, then look for a minimum cost stream between a and b with stream = 2.

---

Someone might think that you can use a simple algorithm to find the shortest path from a to b , remove its edges from the graph, and then find another short path.

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

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