给定一个加权无向图G和两个顶点a, b，我们想要找到两条路径一个 -> 乙 and b -> a使得它们不共享任何边，并且两条路径中边的权重之和最小。最多可以有1,000顶点，直到10,000 edges.
我最初尝试提出一种动态编程方法，但找不到这样的方法。任何想法/建议将不胜感激。
This is 最小成本流问题。您可以为每条边分配等于 1 的流容量，然后搜索之间的最小成本流a and b流量=2。
有人可能认为可以使用简单的算法来找到最短路径a to b，从图中删除其边，然后找到另一条最短路径。
这种方法并不总是最佳的。对于某些图表，它给出了很好的近似值。对于其他人来说，它可能会给出一个非常糟糕的解决方案：
在移除第一条最短路径（绿色）的边缘后，唯一剩下的路径（红色）非常重。该方案的成本为1+1+10+1+1+2+90+2=108。而最优成本是1+15+1+2+1+10+1+2=32。
