具有流容量节点的图的Edmonds-Karp算法

Question

我正在为一个有向图实现这个算法。但有趣的是，这个图节点也有自己的流量能力。我想，这个原来问题的微妙变化，一定要用特殊的方式来处理。因为，在原始的最大流问题中，从开始到结束寻找任何路径都是可以的(实际上，在Edmonds-Karp算法中，我们需要做BFS，并选择到达最终节点的第一条路径)，但是对于这个节点容量扩展，我们需要更多地注意“此路径选择”作业。我知道这一点是因为，我实现了原始算法，发现自己获得的流值比max-flow小，我怀疑这与节点容量限制有关。

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

任何想法都将不胜感激。

提前谢谢。

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

很明显，得到的最大流就是解决方案(而且证明起来也不是特别困难)。