Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2012:journals:jeanpaul:chaptersevensectioni [2012/04/02 10:52] – created mugabej | courses:cs211:winter2012:journals:jeanpaul:chaptersevensectioni [2012/04/02 11:03] (current) – [The Problem] mugabej | ||
|---|---|---|---|
| Line 46: | Line 46: | ||
| --> Residual edges with positive residual capacity\\ | --> Residual edges with positive residual capacity\\ | ||
| --> E< | --> E< | ||
| + | \\ | ||
| + | **Augmenting Path Algorithm**\\ | ||
| + | --> Ford-Fulkerson(G, | ||
| + | --> foreach e ∈ E f(e) = 0 # initially no flow\\ | ||
| + | --> Gf = residual graph\\ | ||
| + | --> while there exists augmenting path P\\ | ||
| + | .f = Augment(f, c, P) # change the flow\\ | ||
| + | .update Gf # build a new residual graph\\ | ||
| + | --> return f\\ | ||
| + | Augment(f, c, P) | ||
| + | --> b = bottleneck(P) # edge on P with least capacity\\ | ||
| + | --> foreach e ∈ P\\ | ||
| + | .if (e ∈ E) f(e) = f(e) + b # forward edge, forward flow\\ | ||
| + | .else f(eR) = f(e) - b # forward edge, backward flow\\ | ||
| + | --> return f\\ | ||
| + | ** Analyzing the Algorithm**\\ | ||
| + | \\ | ||
| + | --> At every intermediate stage of the Ford-Fulkerson Algorithm, the flow values {f(e)} and the residual capacities in G< | ||
| + | --> With the above assumption, the Ford-Fulkerson Algorithm terminates in at most C iterations of the While loop.\\ | ||
| + | --> And the Algorithm can be implemented to run in O(mC) time.\\ | ||
| + | |||
| + | Reading this section outside class time helped me a lot. In all fairness, I was lost in lectures as things were fast in a very bad week for me. I was delighted to read this section and see things gradually unfold and start making sense.\\ | ||
| + | For this very reason, I give this section an 9/10. | ||
