Edmonds–Karp algorithm: Difference between revisions

Revision as of 06:10, 19 March 2025

Revision as of 12:33, 24 March 2025

Line 9:

The proof first establishes that distance of the shortest path from the source node {{mvar|s}} to any non-sink node {{mvar|v}} 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\left( \frac{|V||E|}{2} \right) \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 {{mvar|s}} to {{mvar|v}} to ''decrease''. Let {{mvar|f}} be the flow before such an aumentationaugmentation and <math>f'</math> be the flow after. Denote the minimum distance in a residual flow network {{tmath|G_f}} from nodes <math>u, v</math> as <math>\delta_f (u, v)</math>. One can derive a conttradictioncontradiction by showing that <math>\delta_f (s, v) \leq \delta _{f'} (s, v)</math>, meaning that the shortest path distance between source node {{mvar|s}} and non-sink node {{mvar|v}} did not in fact decrease. <ref name='clrs'/>

==Pseudocode==