最短两个不相交的路径; 两个源和两个目的地(Shortest two disjoint path

我们给出一个未加权无向图G =（V，E），其中| V | <= 40000和| E | <= 10 ^6。 我们也给出了四个顶点A，B，A 'B'。 有没有找到两个节点分离路径的一种方式- > A“和B - > B”，使得它们的长度之和最小？
我首先想到的是先找到最短路径- >一“从图中删除它，然后找到最短路径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和b之间的最小成本的流量= 2）。 如果一个 ！= B，您只需创建一个共同的源节点和A和B连接到它。 如果“！= B”，做同样的一个共同的目的地节点。

但是，如果一个 ！= B和A“！= B”，最小代价流问题不适用。 相反，这个问题可以得到解决的多商品流问题 。

---

我以前的（不正确的）的解决方案是两对（A，B）和（A“ B”），以共同的源/目的节点连接，然后找到最小费用流。 下图是一个反例这种方法：

Answer 2:

这个怎么样？ 做BFS从A1（广度优先搜索）穿越 - > a2和删除路径和计算BFS B1 - > B2。 现在重置图形，并用B1-> B2第一和移除路径，然后执行相同的A1-> A2。 无论总和minumum就是答案。

文章来源: Shortest two disjoint paths; two sources and two destinations