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

Question

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

我最初试图提出一种动态编程方法，但找不到。任何想法/建议将不胜感激。

Answer 1

这就是最小成本流问题。您可以为每条边分配等于 1 的流量容量，然后在a和b之间搜索流量 = 2 的最小成本流量。

---

有人可能认为可以使用简单的算法找到从a到b的最短路径，从图中删除它的边，然后再找到另一条最短路径。

这种方法并不总是最优的。对于某些图表，它提供了很好的近似值。对于其他人，它可能会给出一个非常糟糕的解决方案：

在去除第一条最短路径（绿色）的边缘之后，唯一剩下的路径（红色）非常重。该方案的成本为1+1+10+1+1+2+90+2=108。而最优成本是 1+15+1+2+1+10+1+2=32。