algorithm - 具有具有流动能力的节点的图的 Edmonds-Karp 算法

Question

我正在为一个有向图实现这个算法。但有趣的是，这个图节点也有自己的流量。我认为，必须以特殊的方式处理原始问题的这种细微变化。因为，在最初的最大流问题中，可以找到从头到尾的任何路径(实际上，在 Edmonds-Karp 算法中，我们需要进行 BFS，并选择到达最终节点的第一条路径)但是对于这个节点 -能力延伸，我们需要更加谨慎地对待“这个路径选择”工作。我知道这是因为，我实现了原始算法并发现自己得到的流量值小于最大流量，我怀疑这与节点容量限制有关。

我为此付出了很多努力，并提出了一些想法，例如通过添加自循环(向每个节点添加自循环并找到包含此自循环的路径)将初始图转换为对节点没有容量限制的图为路径上的每个节点循环)或添加权重取代初始节点容量约束的虚拟节点和边)但是，我不相信这些都是解决这个问题的好方法。

任何想法将不胜感激。

提前致谢。

Answer 1

从具有节点容量的最大流量问题到常规最大流量问题有一个简单的减少:

对于图中的每个顶点 v，替换为两个顶点 v_in 和 v_out。 v 的每个传入边都应指向 v_in，并且 v 的每个传出边都应指向 v_out。然后创建一条从 v_in 到 v_out 的附加边，其容量为 c_v，即顶点 v 的容量。

因此，您只需在转换后的图上运行 Edmunds-Karp。

假设您的问题中有以下图表(顶点 v 的容量为 2):

s --> v --> t
   1  2  1

这对应于最大流问题中的这张图:

s --> v_in --> v_out --> t
   1        2         1

很明显，获得的最大流量就是解决方案(证明两者都不是特别困难)。