9

我正在为有向图实现此算法。但是这个图节点的有趣之处也有它们自己的流量能力。我认为，必须以特殊的方式处理原始问题的这种细微变化。因为，在原始的最大流问题中，从头到尾找到任何路径都可以（实际上，在 Edmonds-Karp 算法中，我们需要做 BFS，并选择到达最终节点的第一条路径）但是有了这个节点-容量扩展，我们需要更加小心“这条路径选择”的工作。我知道是因为，我实现了原始算法，发现自己的流量值比最大流量小，我怀疑这与节点容量限制有关。

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

任何想法将不胜感激。

提前致谢。

4

1 回答 1

13

从节点容量的最大流量问题到常规最大流量问题有一个简单的简化：

对于图中的每个顶点v，用两个顶点v_in和替换v_out。每个传入边 tov应该指向v_in并且每个传出边 fromv应该指向 from v_out。然后创建一个额外的边 from v_into v_outwith capacity c_v，即 vertex 的容量v。

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

因此，假设您的问题中有以下图表（顶点v的容量为 2）：

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

这将对应于最大流问题中的此图：

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

很明显，获得的最大流量就是解决方案（而且证明也不是特别困难）。

于 2012-01-06T00:36:00.183 回答