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:
- 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)