The normal Ford-Fulkerson method finds augmenting paths (as long as one exists) while including "back-flows", but if those back-flows are ignored, does there exist a flow network for which algorithm will not terminate? Assume integer capacities for each edge.

Edit: I learned that even if the back-flows are ignored, with each iteration of the algorithm, we need to show that the capacity of at least one edge will decrease. If this is the case, then when continuously iterating through and finding paths within the network, we will eventually get to a point where all edges become "filled" in the worst case. When this happens, the algorithm must terminate.

  • $\begingroup$ Welcome to CS.StackExchange! What have you tried towards the solving the problem so far? You should include it in the question description. $\endgroup$ Commented Nov 20, 2017 at 6:30
  • $\begingroup$ I updated the question now $\endgroup$
    – Dr C
    Commented Nov 21, 2017 at 1:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.