0
$\begingroup$

Does ford fulkerson only use whole numbers? I tried to understand this but without success

Thank you

$\endgroup$
  • $\begingroup$ There are many network flow algorithms. You may want to clarify whether algorithms other than Ford-Fulkerson algorithm are covered. $\endgroup$ – John L. Jan 1 '19 at 21:56
1
$\begingroup$

Since all steps of the algorithm merely involve addition, you can compute the least common multiple $m$ of the denominators of all weights involved, and creating $G'$ from $G$ by multiplying all weights by $m$.

Then all weights are integers and you can run Ford-Fulkerson. You can divide the results from it by $m$ again to get back your rationals.

$\endgroup$

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.