如何在加权无向图中找到包含两个给定节点的最小加权环？

Question

3

给定一个带权无向图 G = (V, E) 和一组节点 P。

给定两个节点 n1 和 n2。

我想找到两条不重叠的路径，从 n1 到 n2，使得这两条路径的权值和最小。并且将问题简化为所描述的标题，即包含 n1 和 n2 的最小权重环。

显然，先找到从 n1 到 n2 的第一条最小权重路径 p1，然后从图中删除路径 p1 上的边，再找到第二条最小权重路径 p2 是不正确的。

如何找到这样的环？

- Tian Wang

你目前有什么进展？ - fuesika

@fuesika 目前还没有想法...:( - Tian Wang

@fuesika 这是一个典型的最小费用最大流问题。你也可以搜索这个问题的答案，它描述了和我的问题相同的情况。 - Tian Wang

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

问题可以使用流网络来解决。请参考Edmonds-Karp算法：它涉及在每个步骤中计算增广路径。

像Edmonds-Karp算法中描述的那样，使用广度优先搜索找到增广路径（如果您的图是加权的，请使用Bellman-Ford）。

然后，以同样的方式找到另一个增广路径。消除出现在两条路径中的边缘（流算法实际上会为您处理此操作），这将是您的循环。基本上，如果将所有边缘容量设置为1，则您的循环将包括您已经推动1流量的边缘。

如果你不喜欢基于流的解决方案，这里有另一种方式。它基本上是相同的东西，只是不是基于流算法。

使用任何可行的算法（如果没有负权重则使用Dijkstra，否则使用Bellman-Ford）找到连接n1和n2的最短路径；
将这条最短路径上的边替换为从n2指向n1的有向弧。例如，如果你的最短路径是n1 -> x -> y -> z -> n2，则将边(n1，x)替换为有向弧x -> n1，(x，y)替换为有向弧y -> x等。
同时将这些弧的权重取反。例如，如果(x，y)的权重为c，则有向弧y -> x的权重将为-c。
在这个新图中从n1到n2找到最短路径。现在你需要使用一个能够处理负权重的算法。
删除出现在两条最短路径中的边。你所剩下的就是你要找的循环。