network flow problem--minimize weight of the edges in graph such that every special node has a flow 1

483 Views Asked by At

Assume at first there is an unweighted graph. We have a source in this graph and we want to send flow with value one to the special nodes specified before, so you must weigh the edges. If you put all the edges equal to infinity you can do this, but we want minimum weight for edges.

my solution: At first I put another source and connect the source to the special nodes with edges equal to 1 and other edges in the graph have infinite value. Then run the Ford Fulkerson algorithm in the graph. after doing this algorithm, every edge has a flow and I set the flow of the edges to the weight of that edges. But this doesn't meke the weight of the edges minimal.

How is this problem solved? Is this related to a famous problem?

0

There are 0 best solutions below