c Balaji Raghavachari 200 Algorithm Design and Analysis c Balaji Raghavachari 201 Algorithm Design and Analysis Augmenting path 12 a Flow example b 7 15 3 s 12 a 4 b 7 15 3 s 5 c d 10 10 c Balaji Raghavachari 202 Algorithm Design and Analysis 4 12 c Balaji Raghavachari a 4 7 s 4 5 4 10 d 4 12 b 4 7 3 t c Algorithm Design and Analysis 15 3 4 4 203 Another augmenting path of capacity 3 b 15 10 10 In the example path s c d a b t is an augmenting path Capacity of path is the minimum residual capacity of its edges in example it is 4 Flow of 4 units a d Find augmenting path from s to t a path in which the residual capacity of all edges are positive 5 c Residual capacity of an edge cf u v c u v f u v extra ow that could be sent through u v t 4 t s 10 t 4 4 4 5 c 4 10 d 10 c Balaji Raghavachari 204 Algorithm Design and Analysis c Balaji Raghavachari 7 12 a b 4 7 3 15 3 3 s 4 4 4 5 c 7 10 d c Balaji Raghavachari 206 7 12 b 3 15 t 4 4 Algorithm Design and Analysis 4 7 3 3 s 3 10 Algorithm Design and Analysis Augmenting path of 3 units Flow of 7 units a 205 4 5 c 7 10 d t 3 10 c Balaji Raghavachari 207 Algorithm Design and Analysis A blocking ow a Flow of 10 units 10 12 7 7 3 3 7 7 3 3 s 4 4 4 4 b 6 15 4 5 c 7 10 d b 6 15 s a 10 12 t 4 5 c 7 10 d t 3 10 Observe that any directed path from s to t has to go through a saturated edge f u v c u v 3 10 Blocking ow a ow in which any directed path from s to t has a saturated edge A blocking ow may not be a maximum ow Therefore the greedy algorithm fails to nd a maximum ow c Balaji Raghavachari 208 Algorithm Design and Analysis c Balaji Raghavachari 209 Algorithm Design and Analysis Augmenting path that pushes ow against direction of edge It is possible to augment ow by pushing ow back on some edge For example consider the path s a d t 10 12 a Flow of 14 units b 7 7 6 15 3 3 s c 3 10 d 4 4 We can send ow from a to d by reducing the ow from d to a up to 4 units the ow from d to a Residual capacity cf a d f d a 4 c Balaji Raghavachari 210 Algorithm Design and Analysis 10 15 10 12 0 5 c 7 10 d 7 10 7 10 c Balaji Raghavachari 211 Algorithm Design and Analysis 2 Construct residual network Gf For each edge u v E add edge u v to Gf with residual capacity cf u v c u v f u v t Add reverse edge v u with cf v u f u v 7 10 Aggregate capacities of multiple edges in same direction Drop edges with zero residual capacity T 3 If there is no path in Gf from s to t stop Consider cut S s a b and T c d t All edges from S to T are saturated All edges from T to S have no ow Therefore ow is a maximum ow of 14 units d 1 Start with an empty ow f f u v 0 for u v E b 3 3 S 4 4 c Ford Fulkerson s algorithm 7 7 s 0 5 t Is this a maximum ow Proof of maximum ow a 7 7 3 3 s 7 10 b 10 15 t 4 5 4 4 10 12 a 4 Otherwise nd a path P from s to t and augment ow along P for all edges u v P set f u v f u v p or f v u f v u p where p mine P cf e Edmonds Karp algorithm use BFS to nd path in Gf from s to t Repeat steps 2 4 until done c Balaji Raghavachari 212 Algorithm Design and Analysis c Balaji Raghavachari 213 Algorithm Design and Analysis Residual network Gf of ow in Slide 206 a 10 12 b 6 15 Illustration of Edmonds Karp algorithm 7 7 3 3 s 4 5 4 4 c 7 10 d t 3 10 a 15 12 2 9 10 6 s 7 7 c a 15 t 3 4 4 c 3 1 7 214 a 7 15 Algorithm Design and Analysis 7 12 3 s c c a 8 d 10 5 b 7 3 7 4 7 15 c a 7 12 b 3 s 4 4 d 10 c 4 10 d 4 10 c a 10 15 5 b 7 4 6 10 12 c 7 7 4 t a c d 7 10 2 10 10 s b 5 5 4 d 3 3 4 4 7 7 t 6 5 7 3 7 3 s 10 4 10 10 Algorithm Design and Analysis 7 s t 5 a 8 t 5 t d 10 215 7 7 7 7 c Balaji Raghavachari t 5 4 s b b 5 3 c Balaji Raghavachari 12 3 4 Augmenting path s a d t is a path from s to t in Gf 10 d 10 s d t 5 4 b 7 3 s a b 7 10 b 7 3 t 3 5 d 7
View Full Document
Unlocking...