Content deleted Content added
Thomas Meng (talk | contribs) →Algorithm: wikilink proof by contradiction |
Thomas Meng (talk | contribs) →Algorithm: some nuances in wording |
||
Line 8:
<ref name='clrs'>{{cite book |author=[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]] and [[Clifford Stein]] |title=Introduction to Algorithms |publisher=MIT Press | year = 2009 |isbn=978-0-262-03384-8 |edition=third |chapter=26.2 |pages=727–730 |title-link=Introduction to Algorithms }}</ref>. A proof outline using these properties is as follows:
The proof first establishes that distance of the shortest path from the source node <math>s</math> to any non-sink node <math>v</math> in a residual flow network increases monotoically after each augmenting iteration (Lemma 1, proven below). Then, it shows that the each of the <math>|E|</math> edges can be critical at most <math>\frac{|V|}{2}</math> times for the duration of the algorithm, giving an upper-bound of <math>O( \frac{|V||E|}{2} ) \in O(|V||E|)</math> augmenting iterations. Since each iteration takes <math>O(|E|)</math> time (bounded by the time for finding the shortest path using Breadth-First-Search), the total running time of Edmonds-Karp is <math>O(|V||E|^2)</math> as required. <ref name='clrs'/>
To prove Lemma 1, one can use [[proof by contradiction]] by assuming that there is an augmenting iteration that causes the shortest path distance from <math>s</math> to <math>v</math> to ''decrease''. Let <math>f</math> be the flow before such an aumentation and <math>f'</math> be the flow after. Denote the minimum distance in a residual flow network <math>G_f</math> from nodes <math>u, v</math> as <math>\delta_f (u, v)</math>. One can derive a conttradiction by showing that <math>\delta_f (s, v) \leq \delta _{f'} (s, v)</math>, meaning that the shortest path distance between source node <math>s</math> and non-sink node <math>v</math> did not in fact decrease. <ref name='clrs'/>
| |||