The shortest two disjoint paths; two sources and two destinations

Question

We are assigned an unweighted undirected graph G = (V, E) , where | V | <= 40,000 and | E | <= 10 ⁶ . We are also given four vertices a, b, a ', b' . Is there a way to find two node-disjoint paths a → a ' and b → b' so that the sum of their lengths is minimal?
My first thought was to first find the shortest path a → a ' , remove it from the graph, and then find the shortest path b → b' . I do not think this greedy approach will work.

Note. . Throughout the application, a and b are fixed, and a and b ' in each request, so a solution that uses precomputing to provide an efficient request will be preferred. Note also that only the minimum sum of lengths is required, not the actual paths.

Any help, ideas or suggestions would be greatly appreciated. Thank you very much in advance!

Answer 1

This can be reduced to the problem of the shortest problems with boundaries:

• (optional) Collapse all chains in the graph into separate edges. This creates a smaller weighted graph (if there are chains in the original graph).
• Convert an undirected graph to a digraph by replacing each edge with a pair of directed edges.
• Divide each node into a pair of nodes: one with only incoming edges of the source node, the other with only outgoing edges. Connect each pair of nodes with one directional edge. (For example, node c in the diagram below should be divided into c1 and c2 ; now each path contains node c in the source graph must go through the edge c1 → c2 in the transformed graph, here x and y represent all the nodes in the graph except node c ).

Now, if a = b or a = b ' , you get exactly the same problem as in the previous question (which is a problem with minimal costs and can be solved by setting the throughput for each edge equal to 1, then to search for a stream minimum cost between a and b with flow = 2). If a ! = B , you simply create a generic source node and connect both a and b to this. If a ' ! = B' , do the same with the generic destination address of the node.

But if a ! = B and a ! = B ' , the minimum cost problem is not applicable. Instead, this problem can be solved as a problem with several products .

---

My previous (wrong) solution was to connect both pairs ( a , b ) and ( a ' , b' ) to common source / target nodes, then find the stream with minimal cost. The following graph is a counter example for this approach:

Answer 2

How about this? Carry out a BFS (search in the width of the first search) with a1 → a2 and delete the path and calculate BFS b1 → b2. Now reset the graph and do the same with b1-> b2 first and delete the path and then a1-> a2. Whatever the minimum amount, this is the answer.