Edmonds-Karp algorithm for a graph that has nodes with bandwidth

Question

I am implementing this algorithm for a directed graph. But the interesting thing about these nodes of the graph also has its own flow capabilities. I think this subtle change in the original problem should be addressed in a special way. Because in the original problem with the maximum flow, it was normal to find any path from beginning to end (in fact, in the Edmond-Karp algorithm we need to make BFS and select the first path that will reach the final node). But with this node -capacity, we need to be more careful in the task of choosing this path. I know this because, I implemented the original algorithm and found that I am getting lower flow values ​​than max-flow, I doubt that it is related to node -capacity restrictions.

I put a lot of effort into this and came up with some ideas, such as converting the initial graph to a graph that has no bandwidth restrictions on nodes, adding custom loops (adding custom loops to each node and search paths that include these self-loops for each node on the path) or adding virtual nodes and edges whose weights replace the initial node -capacity constraints). However, I am not sure if any of them is a good solution to this problem.

Any idea would be greatly appreciated.

Thanks in advance.

Answer 1

There is a simple shortcut from the max flow problem with node capacity to the regular max flow problem:

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

, ( ).