Consider the following simple network with edge capacities as shown. Show that,
ID: 3655692 • Letter: C
Question
Consider the following simple network with edge capacities as shown. Show that, if the Ford-Fullkerson algorithm is run on this graph, a careless choice of updates might cause it to take 1000 iterations. Imagine if the capacities were a million instead of 1000.Explanation / Answer
In the Ford-Fulkerson algorithm, we can choose any arbitrary augmenting path from the source to the sink, so the path S->A->B->T can be used to augment the flow by one. This would then create a reverse path from B->A of weight 1. The next iteration, we could hypothetically choose a path of S->B->A->T of weight 1. We can continue selecting augmenting paths in this manner 999 more times.