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

Question

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

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

任何帮助,想法或建议都将非常感激.非常感谢提前!

Answer 1

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

1. (可选)将图表中的所有链折叠成单个边.这会产生较小的加权图(如果原始图中有任何链).
2. 通过用一对有向边代替每个边来将无向图变换为有向图.
3. 将每个节点拆分为一对节点:一个节点只有原始节点的入口边缘,另一个节点只有其出局边缘.使用单个有向边连接每对节点.(例如,下图中的节点c应该分为c1和c2 ;现在原始图中包含节点c的每个路径都应该通过变换图中的边c1 - > c2 ;这里x和y代表所有节点除了节点c)之外的图形.

现在,如果a = b或' = b',您将得到与上一个问题完全相同的问题(这是最小成本流问题,可以通过为每个边等于1分配流量来解决,然后搜索a和b之间的最小成本流量,流量= 2).如果是!= b,您只需创建一个公共源节点并将a和b连接到它.如果是'!= b',请对公共目标节点执行相同操作.

但如果a!= b和'!= b',则最低成本流量问题不适用.相反,这个问题可以解决为多商品流问题.

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