最短两个不相交的路径;两个源和两个目的地 [英] Shortest two disjoint paths; two sources and two destinations

问题描述

我们正在给一个加权无向图中的的 G =（V，E）的，其中 | V | ＆LT; = 40000 和 | E | ＆LT; = 10 ⁶ 。我们也给出了四个顶点的 A，B，A'，B'。有没有办法找到两个节点分离路径 - >一个和 B - > B'？使得它们的长度之和最小
我首先想到的是先找到最短路径 - >一个，从图中删除它，然后找到最短路径的 B - > B'。我不认为这贪婪的方法是可行的。

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.

注意：在整个应用程序， 和 B 是固定的，而 和 b位变化在每个查询，以便使用precomputing以便提供高效的查询将是preferable的溶液。还要注意的是，需要的长度只有最小总和，而不是实际的路径。

Note: Throughout the application, a and b are fixed, while a' and b' change at each query, so a solution that uses precomputing in order to provide efficient querying would be preferable. Note also that only the minimum sum of lengths is needed, not the actual paths.

任何帮助，意见或建议将是非常美联社preciated。感谢很多提前！

Any help, ideas, or suggestions would be extremely appreciated. Thanks a lot in advance!

推荐答案

这可以减少到最短边不相交的路径问题：

This may be reduced to the shortest edge-disjoint paths problem:

1. （可选）收起图中的成单刃所有连锁。这将产生一个较小的加权图（如果有在原始图中的任何链）。
2. 变换无向图到有向图由一对向边替换每个边缘。
3. 分割各个节点到节点对：一个仅传入原始节点的边缘，其他与只有其出边。连接每对节点与单个定向的边缘。 （例如，节点的 C 下图中应分为 C1 和 C2 ;现在包含节点的ç每个路径在原来的图形应通过边 C1 - > C2 在变换曲线;这里的 X 和是重present除节点图中的所有节点的 C ）。

1. (Optionally) Collapse all chains in the graph into single edges. This produces a smaller weighted graph (if there are any chains in the original graph).
2. Transform undirected graph into digraph by substituting each edge by a pair of directed edges.
3. Split each node into the pair of nodes: one with only incoming edges of the original node, other with only its outgoing edges. Connect each pair of nodes with a single directed edge. (For example, node c in the diagram below should be split into c1 and c2; now every path containing node c in the original graph should pass through the edge c1 -> c2 in the transformed graph; here x and y represent all nodes in the graph except node c).

现在，如果 = <强> B 或 = B'，你会得到完全同样的问题在 previous问题（是的最小成本流问题并可以通过分配流容量为每个边缘等于1，则搜索具有流a和b之间的最小代价流来解决= 2）。如果 ！= <强> B ，您只需创建一个共同的源节点和两个 和 B 连接。如果 ！= B'，有一个共同的目的节点做同样的。

Now if a = b or a' = b', you get exactly the same problem as in your previous question (which is Minimum-cost flow problem and may be solved by assigning flow capacity for each edge equal to 1, then searching for a minimum-cost flow between a and b with flow=2). If a != b, you just create a common source node and connect both a and b to it. If a' != b', do the same with a common destination node.

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

But if a != b and a' != b', minimum-cost flow problem is not applicable. Instead this problem may be solved as Multi-commodity flow problem.

我的previous（不正确）的解决方案是连接两对（ B ）和（ ，< STRONG> B'），以共同的源/目的节点，然后找到一个最小代价流。下图是一个反例这种方法：

My previous (incorrect) solution was to connect both pairs of (a, b) and (a', b') to common source/destination nodes, then to find a minimum-cost flow. Following graph is a counter-example for this approach:

这篇关于最短两个不相交的路径;两个源和两个目的地的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！