[prev] 78 [next]

Edmonds-Karp Algorithm (cont)

Time complexity analysis …
  • Theorem.   The number of augmenting paths needed is at most V·E/2.
    ⇒ Outer loop has O(V·E) iterations.
  • Finding augmenting path   ⇒ O(E)    (consider only vertices connected to source and sink ⇒ O(V+E)=O(E))
Overall cost of Edmonds-Karp algorithm: O(V·E2)

Note: Edmonds-Karp algorithm is an implementation of general Ford-Fulkerson method