I am trying to implement max-flow with vertex capacities in addition to edge's capacities.
I found in wiki a reduction to a new graph G where each vertex corresponds to v_in and v_out and some appropriate changes to the edges .
My initial implementation did something else and I am wondering if it is wrong .
In the step that the original ford-fulkerson examines a path it increases the flow of the path with respect to the edge of minimum capacity in this path (we cannot exceed that).
What if I also found the minimum vertex capacity in this path ? The largest between these quantities (max(b(v)) and max(b(e)) for v and e in path p) would define the maximum flow that can run through that path , wouldn't it ?
And the complexity remains the same .
Max flow with vertex capacities without reduction
Viewed 56
2 Answers
A lot of graph algorithms are described in terms of making a new graph, but then in practical implementations we try to optimize that step away.
That sounds like what you're doing: Does every augmenting path that you find in your flow graph correspond to a valid augmenting path in the (now imaginary) new graph? If so, then your algorithm is fine.
The main reason to use split node technique is because most of the time max-flow algorithms are used as a black box You don't want to change the algorithm implementation that's why you split the nodes.
Your algorithm is definitely correct.
Related