Ford-Fulkerson Algorithm is a 202204151143# aim to solve #202206091105 by repeatedly finds augmenting paths through the 202206091605# and augments (updates) the flow until there is no 202206091601# to be found. It is essentially finding the bottlenecks, that is the smallest maximum capacity in the augmenting path, and sum them all together to get the maximum flow for the #202204112045. 1
Details
Augments (update) the flow means updating the flow values of the edges along the 202206091601#. This can be done by simply increasing the flow to the forward edges and decreasing the flow to the 202206091616# by the bottleneck value (the smallest maximum capacity in the path).
Analysis
Assuming this algorithm be implemented in #202205021959, the time complexity will be \(O(fE)\) where \(f\) denotes the maximum flow and \(E\) denotes the number of edges. However, when meeting the worst case as shown below, if the algorithm repeatedly choosing the edge with the smallest maximum capacity (in this case, edge with a value of maximum capacity of 1), it will need 2000 steps to get the maximum flow. This turn out to be a rather poor performance.
Aug 2018 https://www.youtube.com/watch?v=LdOnanfc5TM