最短的两条不相交路径；两个起点和两个终点。

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' 在每个查询时都会改变，因此最好使用预计算来提供高效的查询解决方案。另请注意，只需要长度之和的最小值，而不需要实际路径。

非常感谢任何帮助、想法或建议！

- Chris

---

无法工作是因为最短路径a->a'可能通过一个节点，这是从b到b'的唯一路径。在预处理阶段，您可以存储图中每个节点与a和b之间的最小距离。 - Gir

@Gir 是的，那很有道理。 - Chris

可能并不是很有帮助，但我想指出即使任意两个节点之间都存在路径（想象一下有两个图，一个包含a和b，另一个包含a'和b'，还有一个额外的节点是连接这两个图的唯一方式），也有可能不存在解决方案。 - Scott Hunter

有一本书叫做《Survivable Networks: Algorithms for Diverse Routing》，它为这些问题提供了很好的介绍和解决方案。这里是它在谷歌图书上的链接：http://books.google.com.hk/books?hl=en&lr=&id=SIkfR0lAN1wC&oi=fnd&pg=PR11&ots=LQJxh2ghfa&sig=9PjKDkP0SaO6_rcMbHZ_bQBR5O8&redir_esc=y&hl=zh-CN&sourceid=cndr#v=onepage&q&f=false。 - JackeyLyu

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，只需创建一个公共源节点，并将a和b连接到它。如果 a' != b'，则使用公共目标节点执行相同操作。

但是，如果 a != b 并且 a' != b'，则无法应用最小成本流问题。相反，该问题可以作为 Multi-commodity flow problem 解决。

---

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

- Evgeny Kluev

Answer 2

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

- Ankush

---

这个不起作用；反例有点太长了，无法在评论中说明。 - Beta