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

这与max-flow问题中的这个图对应:

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

显而易见的是,获得的最大流量是解决方案(并且证明它也不是特别困难).