Hey i am stuck in a problem where i need to find the maximum flow in a bipartite graph but the weight for the edges in not unity how to do so ? need help @xellos0 @anudeep2011 @adurysk @kuruma @darkshadows @prateekg603
@mugurelionut
Depending on constraints, Ford-Fulkerson might work (it works for general graphs, not just bipartite ones). I suppose weights means capacities.
All you have to do is a BFS on edges with non-zero weight; for each vertex to which there’s a path along them from the source, remember which vertex was before it in that path and the minimum of weights on that path (you don’t need to maximize that minimum). Then, if there’s a path to the sink, send a flow equal to the minimum of weights on it along it and repeat the BFS until you can’t find any other path.
This way, you can consider it an O(N^3) algorithm; it’s possible to implement it in O(NM) as well.
1 Like