CODEWITHSUNDEEP
algorithmasymptotic-complexityedmonds-karp
rishabh mittal
rishabh mittal

Reputation: 71

Complexity of Edmonds-Karp algorithm

Edmonds-Karp algorithm says that shortest distance between source s and sink t is increases monotonically every time shortest path is augmented. With this assumption distance between source s and sink t is going to be not more then |V| - 1. I think it means that there would be no more path between source S and sink T after |V| - 1 augmentation. If this is true , then complexity of finding maximum flow would be (|V| - 1) * E.

I know i wrongly assumed something above. But couldn't understand what it is. Can anyone help me ?

Upvotes: 1

Views: 942

Answers (2)

Shalok Sharma
Shalok Sharma

Reputation: 11

The Edmonds-Karp algorithm uses the concept of augmenting paths, with each new shortest path increasing distance between the source s and the sink t. However, there are some misconceptions in your reasoning:

  1. Path Limit: The assumption that no more paths will exist after |V| - 1 augmentation is incorrect. Actually, the maximum number of augmenting paths will be O(VE). This is because, in each iteration, finding an augmenting path requires a Breadth-First Search (BFS) over the graph, which has a time complexity of O(E). The overall time complexity of the Edmonds-Karp algorithm is O(VE^2). This is derieved from having upto |V| - 1 augmentations multiplied by the O(E) BS operations to find each augmenting path.

To further clarify, following terms can be classified as the following:\

  • Each BFS to find an augmenting path: Since the BFS explores all edges in the graph, its complexity is O(E), where E is the number of edges.
  • Path Length: The length of the augmenting path is at most |V| -1 in terms of edges.
  • Number of augmenting paths: O(VE)
  • Overall: O(VE) * O(E) = O(VE^2)

Upvotes: 0

mcdowella
mcdowella

Reputation: 19601

In my copy of Introduction to Algorithms (probably an early edition) they say "increases monotonically" in lemma 27.8 but what they really prove is that if it decreases there is a contradiction. Where they refer to this lemma in theorem 27.9 they just say since DELTAf(x,v) <= DELTAf'(S,v) so it looks like when they say increases monotonically they really mean "does not decrease" or "increases or remains the same". If it can remain the same, you cannot use it to bound the number of iterations as you have done.

Upvotes: 2

Related Questions