Блог пользователя Abu-Gasem1

Can Any One Give Edmonds Karp’s Algorithm Proof
Автор Abu-Gasem1, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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
→ Ответить