Edmonds-Karp具有流量节点的图的算法 [英] Edmonds-Karp Algorithm for a graph which has nodes with flow capacities

问题描述

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

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

任何想法将不胜感激。

预先致谢。

解决方案

从节点容量的最大流问题简化为常规最大流问题：

对于图中的每个顶点 v ，替换为两个顶点 v_in 和 v_out 。每个到 v 的入口边应该指向 v_in ，并且从 v 应该指向 v_out 。然后从容量 c_v 创建一个从 v_in 到 v_out 的额外边>顶点的容量 v 。

所以你只需在变换后的图上运行Edmunds-Karp。 p>

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

  s  - > v  - > t 
 1 2 1 
  

这对应于max-flow问题中的这个图：

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

显而易见，获得的最大流量是解决方案（并且证明这一点并不难）。

I am implementing this algorithm for a directed graph. But the interesting thing about this graph nodes have also their own flow capacities. I think, this subtle change of the original problem must be handled in a special way. Because, In original max-flow problem It was okay to find any path from start to finish(actually, in Edmonds-Karp algorithm, we need to do BFS, and choose the first path that reaches the final node) But with this node-capacity extension, we need to be more careful about 'this path selection' job. I know it because, I implemented the original-algorithm and found myself getting smaller flow values than max-flow, I doubt that it has to do with this node-capacity restrictions.

I put a lot effort on this and came up with some ideas like transforming the initial graph into a graph which has no capacity constraint on nodes by adding self loops (adding self loops to each node and finding paths which includes this self-loops for each node on the path) or adding virtual nodes and edges whose weights supersede the initial node-capacity constraints) However, I am not convinced that any of these are nice solution for this problem.

Any idea would be much appreciated.

Thanks in advance.

解决方案

There's a simple reduction from the max-flow problem with node capacities to a regular max-flow problem:

For every vertex v in your graph, replace with two vertices v_in and v_out. Every incoming edge to v should point to v_in and every outgoing edge from v should point from v_out. Then create one additional edge from v_in to v_out with capacity c_v, the capacity of vertex v.

So you just run Edmunds-Karp on the transformed graph.

So let's say you have the following graph in your problem (vertex v has capacity 2):

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

This would correspond to this graph in the max-flow problem:

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

It should be apparent that the max-flow obtained is the solution (and it's not particularly difficult to prove either).

这篇关于Edmonds-Karp具有流量节点的图的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！