Content deleted Content added
Thomas Meng (talk | contribs) →Algorithm: naming ref |
Thomas Meng (talk | contribs) →Algorithm: wikilink proof by contradiction |
||
Line 10:
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 (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'/>
==Pseudocode==
| |||