Question? Leave a message!




Ford-Fulkerson algorithm

Ford-Fulkerson algorithm
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Website URL
Comment
7. NETWORK FLOW I max-flow and min-cut problems ‣ Ford-Fulkerson algorithm ‣ max-flow min-cut theorem ‣ capacity-scaling algorithm ‣ shortest augmenting paths ‣ blocking-flow algorithm ‣ unit-capacity simple networks ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Sep 8, 2013 6:40 AM7. NETWORK FLOW I max-flow and min-cut problems ‣ Ford-Fulkerson algorithm ‣ max-flow min-cut theorem ‣ capacity-scaling algorithm ‣ shortest augmenting paths ‣ blocking-flow algorithm ‣ unit-capacity simple networks ‣ SECTION 7.1Flow network Abstraction for material flowing through the edges. Digraph G = (V, E) with source s ∈ V and sink t ∈ V. Nonnegative integer capacity c(e) for each e ∈ E. no parallel edges no edge enters s no edge leaves t capacity 9 15 10 4 15 10 s 8 10 t 5 15 6 10 4 15 16 3Minimum cut problem Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B. cap( A, B) = c(e) ∑ e out of A € 10 s t 5 15 capacity = 10 + 5 + 15 = 30 4Minimum cut problem Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B. cap( A, B) = c(e) ∑ e out of A € 10 s t 8 don't count edges from B to A 16 capacity = 10 + 8 + 16 = 34 5Minimum cut problem Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B. cap( A, B) = c(e) ∑ e out of A Min-cut problem. Find a cut of minimum capacity. € 10 s t 8 10 capacity = 10 + 8 + 10 = 28 610 / 15 5 / 10 0 / 6 5 / 15 Maximum flow problem Def. An st-flow (flow) f is a function that satisfies: 0 ≤ f(e) ≤ c(e) For each e ∈ E : capacity f (e) = f (e) ∑ ∑ For each v ∈ V – s, t : flow conservation e in to v e out of v € € capacity flow inflow at v = 5 + 5 + 0 = 10 outflow at v = 10 + 0 = 10 5 / 9 0 / 15 0 / 4 s t 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 10 / 16 7 10 / 10 10 / 10 v10 / 15 5 / 10 0 / 6 5 / 15 Maximum flow problem Def. An st-flow (flow) f is a function that satisfies: 0 ≤ f(e) ≤ c(e) For each e ∈ E : capacity f (e) = f (e) ∑ ∑ For each v ∈ V – s, t : flow conservation e in to v e out of v € v( f ) = f (e) . ∑ Def. The value of a flow f is: val( f ) = e out of s € € 5 / 9 0 / 15 0 / 4 s t 5 / 5 5 / 8 10 / 10 0 / 15 0 / 4 value = 5 + 10 + 10 = 25 10 / 16 8 10 / 10 10 / 1013 / 15 8 / 10 3 / 6 2 / 15 Maximum flow problem Def. An st-flow (flow) f is a function that satisfies: 0 ≤ f(e) ≤ c(e) For each e ∈ E : capacity f (e) = f (e) ∑ ∑ For each v ∈ V – s, t : flow conservation e in to v e out of v € v( f ) = f (e) . ∑ Def. The value of a flow f is: val( f ) = e out of s € Max-flow problem. Find a flow of maximum value. € 8 / 9 0 / 15 0 / 4 s t 5 / 5 8 / 8 10 / 10 0 / 15 0 / 4 value = 8 + 10 + 10 = 28 13 / 16 9 10 / 10 10 / 107. NETWORK FLOW I max-flow and min-cut problems ‣ Ford-Fulkerson algorithm ‣ max-flow min-cut theorem ‣ capacity-scaling algorithm ‣ shortest augmenting paths ‣ blocking-flow algorithm ‣ unit-capacity simple networks ‣ SECTION 7.10 / 10 0 / 8 Towards a max-flow algorithm Greedy algorithm. Start with f (e) = 0 for all edge e ∈ E. Find an s↝t path P where each edge has f (e) c(e). Augment flow along path P. Repeat until you get stuck. flow capacity 0 / 4 network G 0 / 2 0 / 6 value of flow s t 0 0 / 10 0 / 9 0 / 10 11 0 / 100 / 10 8 — 0 / 8 Towards a max-flow algorithm Greedy algorithm. Start with f (e) = 0 for all edge e ∈ E. Find an s↝t path P where each edge has f (e) c(e). Augment flow along path P. Repeat until you get stuck. 0 / 4 network G 0 / 2 0 / 6 8 s — t 0 + 8 = 8 0 / 10 0 / 9 0 / 10 12 8 — 0 / 100 / 10 8 / 8 Towards a max-flow algorithm Greedy algorithm. Start with f (e) = 0 for all edge e ∈ E. Find an s↝t path P where each edge has f (e) c(e). Augment flow along path P. Repeat until you get stuck. 0 / 4 network G 2— 0 / 2 0 / 6 2 2 s — t 8 + 2 = 10 0 / 10 — 0 / 9 8 / 10 13 10 — 8 / 106 — 0 / 10 8 / 8 Towards a max-flow algorithm Greedy algorithm. Start with f (e) = 0 for all edge e ∈ E. Find an s↝t path P where each edge has f (e) c(e). Augment flow along path P. Repeat until you get stuck. 0 / 4 network G 2 / 2 6 — 0 / 6 6 8 s t 10 — 0 / 10 — 2 / 9 10 / 10 + 6 = 16 14 10 / 106 / 10 8 / 8 Towards a max-flow algorithm Greedy algorithm. Start with f (e) = 0 for all edge e ∈ E. Find an s↝t path P where each edge has f (e) c(e). Augment flow along path P. Repeat until you get stuck. ending flow value = 16 0 / 4 network G 2 / 2 6 / 6 s t 16 6 / 10 8 / 9 10 / 10 15 10 / 109 / 10 7 / 8 Towards a max-flow algorithm Greedy algorithm. Start with f (e) = 0 for all edge e ∈ E. Find an s↝t path P where each edge has f (e) c(e). Augment flow along path P. Repeat until you get stuck. but max-flow value = 19 3 / 4 network G 0 / 2 6 / 6 s t 19 9 / 10 9 / 9 10 / 10 16 10 / 10Residual graph Original edge: e = (u, v) ∈ E. original graph G Flow f (e). u 6 / 17 v Capacity c(e). flow capacity Residual edge. "Undo" flow sent. R e = (u, v) and e = (v, u). residual residual graph G f capacity Residual capacity: u v 11 ⎧ c(e)− f (e) if e∈ E 6 c (e) = ⎨ f R f (e) if e ∈ E ⎩ Residual graph: G = (V, E ). f f € where flow on a reverse edge Residual edges with positive residual capacity. negates flow on a forward edge R E = e : f (e) c(e) ∪ e : f (e) 0. f Key property: f ' is a flow in G iff f + f ' is a flow in G. f 17Augmenting path Def. An augmenting path is a simple s↝t path P in the residual graph G . f Def. The bottleneck capacity of an augmenting P is the minimum residual capacity of any edge in P. Key property. Let f be a flow and let P be an augmenting path in G . f Then f ' is a flow and val( f ' ) = val( f ) + bottleneck(G , P). f AUGMENT (f, c, P) ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ b ← bottleneck capacity of path P. FOREACH edge e ∈ P IF (e ∈ E ) f (e) ← f (e) + b. R R ELSE f (e ) ← f (e ) – b. RETURN f. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 18Ford-Fulkerson algorithm Ford-Fulkerson augmenting path algorithm. Start with f (e) = 0 for all edge e ∈ E. Find an augmenting path P in the residual graph G . f Augment flow along path P. Repeat until you get stuck. FORD-FULKERSON (G, s, t, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ FOREACH edge e ∈ E : f (e) ← 0. G ← residual graph. f WHILE (there exists an augmenting path P in G ) f f ← AUGMENT (f, c, P). Update G . f RETURN f. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 190 / 10 10 0 / 8 8 Ford-Fulkerson algorithm demo flow capacity network G 0 / 4 0 / 2 0 / 6 value of flow s t 0 0 / 10 0 / 10 0 / 9 residual graph G f 4 residual capacity 2 6 s 10 t 9 10 20 0 / 10 10