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.
Dijkstra's algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.
A vertex-disjoint path means there is not any same node except the end nodes during the path.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With