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

Question

我们得到一个未加权的无向图G = (V, E)，其中|V| <= 40,000 和 |E| <= 10⁶。我们还获得了四个顶点 a, b, a', b'。有没有办法找到两个节点不相交的路径 a -> a' 和 b -> b' 使得它们的长度之和最小？
我的第一个想法是先找到最短路径a -> a'，将其从图中删除，然后再找到最短路径b -> b'。我认为这种贪婪的方法行不通。

注意:在整个应用中，a和b是固定的，而a'和 b' 在每次查询时都会发生变化，因此使用预计算以提供高效查询的解决方案将更可取。另请注意，只需要最小长度总和，而不是实际路径。

如有任何帮助、想法或建议，我们将不胜感激。非常感谢!

Answer 1

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

1. (可选)将图中的所有链折叠成单个边。这会产生一个更小的加权图(如果原始图中有任何链)。
2. 通过用一对有向边替换每条边，将无向图转换为有向图。
3. 将每个节点分成一对节点:一个只有原始节点的入边，另一个只有出边。用一条有向边连接每对节点。 (例如，下图中的节点c应拆分为c1和c2；现在每条路径都包含节点c 应该通过转换图中的边 c1 -> c2；这里是 x 和 y 表示图中除节点 c 之外的所有节点。

现在，如果 a = b 或 a' = b'，您会遇到与在你的previous question (这是 Minimum-cost flow problem 并且可以通过为每条边分配等于 1 的流量来解决，然后搜索 a 和 b 之间流量 = 2 的最小成本流量)。如果a != b，您只需创建一个公共(public)源节点并将a 和b 连接到它。如果 a' != b'，对公共(public)目标节点执行相同操作。

但是如果a != b 和a' != b'，最小成本流问题不适用。相反，这个问题可能会被解决为 Multi-commodity flow problem .

---

我之前(不正确的)解决方案是连接两对 (a, b) 和 (a', b ') 到公共(public)源/目标节点，然后找到最小成本流。下图是这种方法的反例: