两个指定顶点之间的最短两条不相交路径

Question

给定加权无向图G和两个顶点a,b,我们希望找到两个路径a - > b和b - > a使得它们不共享任何边,并且使得两个路径中的边的权重之和是最低的.最多可以有1,000个顶点,最多可以有10,000个边.

我最初试图想出一种动态编程方法,但找不到这样的方法.任何想法/建议将非常感激.

Answer 1

这是最小成本流量问题.您可以为每条边等于1分配流量,然后在flow = 2的情况下搜索a和b之间的最小成本流量.

有人可能会认为可以使用简单的算法从a到b找到最短路径,从图中移除其边,然后找到另一条最短路径.

这种方法并不总是最佳的.对于某些图表,它给出了一个很好的近似值.对于其他人来说,它可能会给出一个非常糟糕

在去除第一个最短路径(绿色)的边缘之后,唯一剩余的路径(红色)非常重.该解决方案的成本是1 + 1 + 10 + 1 + 1 + 2 + 90 + 2 = 108.虽然最优成本是1 + 15 + 1 + 2 + 1 + 10 + 1 + 2 = 32.