![]() In this case, the total flow is 3, which is not optimal. We get what is called a blocking flow: no more augmenting paths exist. These paths push 2, 2, and 1 units of flow, respectively, for a total flow of 5:Ĭhoosing paths in this order leads to an optimal solution however, what happens if we select $P_3$ first (i.e., before $P_1$ and $P_2$)? In $G$, one possible execution of the above heuristic finds three augmenting paths $P_1$, $P_2$, and $P_3$, in this order. That is, find a path with available capacity, send flow along that path, and repeat. Go to step 1 until no augmenting paths exist.The value of $\Delta$ is determined by the bottleneck of $P$ that is, the edge with minimum available capacity. Push the maximum possible flow $\Delta$ through this path.Pick an arbitrary augmenting path $P$ that goes from the source vertex $s$ to the sink vertex $t$ such that $\forall e \: (e \in P \rightarrow f_e \lt c_e $) that is, all of the edges in $P$ have available capacity.One possible greedy approach is the following: Suppose that we are trying to solve the maximum flow problem for the following network $G$ (where each label $f_e/c_e$ denotes both the flow $f_e$ pushed through an edge $e$ and the capacity $c_e$ of this edge): The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture.
0 Comments
Leave a Reply. |