Abu-Gasem1's blog

Can Any One Give Edmonds Karp’s Algorithm Proof
By Abu-Gasem1, history, 9 years ago, In English

Hey.

Edmonds Karp’s Algorithm :

" It runs in O(VE2) as it can be proven that after O(VE) BFS iterations, all augmenting paths will already be exhausted. "

Can Any One Give A Proof !

Thanks For All.

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

It is a good practice to google it before asking questions

Intuitive proof:

  1. Length(Shortest Path s-t) = 0 to V and never decreases.
  2. To let the length increase by 1, it takes at most E iterations. (Since an iteration exhausts at least an edge)
  3. Total iterations = V * E
→ Reply