1
$\begingroup$

I am given a directed network graph with three fixed verticess where two of these are "inputs" and and one is the "sink". I'm asked to find the maximal flow through the network. How should go about doing this?

I'm familiar with the Ford–Fulkerson algorithm but can it be used when I have two distinct inputs?

How can I get started?

$\endgroup$
2
$\begingroup$

Make a vertex that is the source of the two inputs, and connect this vertex with the input vertices in your problem. Then apply a suited algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If $a$ and $b$ are my inputs and then I add a vertex $v$ which is my new input and then connect it to $a$ and $b$, what capacity should I set to the new edges (va & vb) in order not the mess things up? (Thanks a lot by the way, I really appreciate your answer) $\endgroup$ – John Smith Jan 17 '14 at 12:28
  • 1
    $\begingroup$ Well, you want to make sure they can still function as the original sources. So you can't let $v_a$ have a capacity lower than the input of $a$, but you can't take a capacity higher than the input of $a$ either. So you should take the input of $a$ as the capacity. Same thing for $v_b$. The new source is of course of magnitude input $a$ + input $b$. So the modified problem has the same total input as the original problem. You are very welcome by the way :). $\endgroup$ – Leo Jan 17 '14 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.