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'，您将得到与上一个问题完全相同的问题（这是最小成本流量问题，可以通过将每条边的流量分配为 1 来解决，然后搜索 a a 和 b 之间的最小成本流，流 = 2)。如果a != b，您只需创建一个公共源节点并将a和b连接到它。如果a' != b'，对公共目标节点执行相同操作。

但是如果a != b和a' != b'，最小成本流问题不适用。相反，这个问题可以作为多商品流动问题来解决。

---

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

Answer 2

这个怎么样？从 a1 -> a2 执行 BFS（广度优先搜索）遍历并删除路径并计算 BFS b1 -> b2。现在重置图形并首先对 b1->b2 执行相同操作，然后删除路径，然后删除 a1->a2。无论总和是最小的都是答案。