Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Shortest two disjoint paths between two specified vertices

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.

like image 966
Chris Avatar asked Aug 09 '12 09:08

Chris


People also ask

Which algorithm finds shortest path between two vertices in a graph?

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.

What is a vertex disjoint path?

A vertex-disjoint path means there is not any same node except the end nodes during the path.


1 Answers

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.

like image 58
Evgeny Kluev Avatar answered Sep 28 '22 16:09

Evgeny Kluev