shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

Question

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/).

Everything in the first part of the proof (The section Monotonically increasing path length) makes sense. However, the last part of it is not very convincing (the part I have highlighted with red).

Can someone convince me that it is true that the fact that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $O(E)$".

---

Answer 1

It is no wonder why that you doubt that "the shortest path increases monotonically in the residual graph" implies a "bound on of one iteration of Edmonds-Karp algorithm to $O(|E|)$".

The time bound of $O(|E|)$ has nothing to do with the fact that "the shortest path increases monotonically in the residual graph".

It takes $O(E)$ time to perform one iteration of Edmonds-Karp algorithm, since what it does is mostly a breadth-first search.

(It takes $O(|V| + |E|)$ time for a breadth-first search on a general graph. However, in the case of finding the maximum flow in a flow network, we assume the given network is connected or there is at least one edge incident to every vertex usually. That is, $|E|\ge |V|-1$ or $2|E|\ge|V|$. Then $O(|V|+|E|)=O(|E|)$)