最短的两条不相交路径；两个来源和两个目的地

We're given an unweighted undirected graph G = (V, E) where |V| <= 40,000 and |E| <= 10⁶. We're also given four vertices a, b, a', b'. Is there a way to find two node-disjoint paths a -> a' and b -> b' such that the sum of their lengths is minimum?
My first thought was to first find the shortest path a -> a', delete it from the graph, and then find the shortest path b -> b'. I don't think this greedy approach would work.

Note:在整个申请过程中，a and b是固定的，同时a' and b'每次查询都会发生变化，因此使用预计算来提供高效查询的解决方案将是更好的选择。另请注意，仅需要最小长度总和，而不是实际路径。

任何帮助、想法或建议将不胜感激。预先非常感谢！

这可以简化为最短边不相交路径问题：

1. （可选）将图中的所有链折叠成单边。这会产生一个较小的加权图（如果原始图中存在任何链）。
2. 通过用一对有向边替换每条边，将无向图转换为有向图。
3. 将每个节点拆分为一对节点：一个仅具有原始节点的传入边，另一个仅具有其传出边。使用单个有向边连接每对节点。 （例如，节点c下图中应分为c1 and c2;现在每个路径都包含节点c原图中应该穿过边c1 -> c2在变换后的图中；这里x and y表示图中除节点外的所有节点c).

Now if a = b or a' = b'，你会遇到与你的问题完全相同的问题上一个问题（这是最小成本流问题可以通过为每条边分配等于 1 的流容量，然后搜索 a 和 b 之间的最小成本流（其中 flow=2）来解决。如果a != b，您只需创建一个公共源节点并将两者连接起来a and b到它。如果a' != b'，对公共目标节点执行相同的操作。

But if a != b and a' != b'，最小成本流问题不适用。相反，这个问题可以解决为多商品流通问题.

我之前的（错误的）解决方案是连接两对（a, b) and (a', b'）到公共源/目标节点，然后找到最小成本流。下图是这种方法的反例：