[proofplan] We prove that shortest-path distances from the source in the residual graph never decrease during Edmonds-Karp. Then we track a residual arc direction that becomes critical, meaning it lies on the chosen shortest augmenting path and is saturated by the augmentation. If the same residual arc direction becomes critical again later, the source-distance to its tail has increased by at least $2$. Since finite shortest-path distances are between $0$ and $n-1$, each residual arc direction can be critical only $O(n)$ times; there are at most $2m$ residual arc directions, and every augmentation makes at least one direction critical. [/proofplan] [step:Set up residual arcs and shortest-path distances] For each original directed edge $e=(u,v)\in E$, define two possible residual arc directions associated to $e$: the edge-labeled forward direction $e^+=(e,u,v)$ and the edge-labeled reverse direction $e^-=(e,v,u)$. The edge label $e$ is part of the residual direction, so parallel or antiparallel original edges remain distinct. During the algorithm, let $G_k=(V,A_k)$ denote the residual graph immediately before the $k$-th augmentation, where $A_k$ is the set of edge-labeled residual arc directions with positive residual capacity. Thus $|A_k|\leq 2m$ for every $k$. For each augmentation index $k$, define the distance function $d_k:V\to \{0,1,\dots,n-1\}\cup\{\infty\}$ as follows. For $x\in V$, let $d_k(x)=\operatorname{dist}_{G_k}(s,x)$, where $\operatorname{dist}_{G_k}(s,x)$ is the length, measured in number of arcs, of a shortest directed path from $s$ to $x$ in $G_k$, and let $d_k(x)=\infty$ if no such path exists. Edmonds-Karp chooses an $s$-$t$ path $P_k$ in $G_k$ of length $d_k(t)$ whenever $d_k(t)<\infty$. [/step] [step:Prove that residual shortest-path distances never decrease] We claim that for every augmentation index $k$ and every vertex $x\in V$, \begin{align*} d_{k+1}(x)\geq d_k(x), \end{align*} with the convention that every integer is less than $\infty$. If $x$ is unreachable from $s$ in $G_{k+1}$, then $d_{k+1}(x)=\infty$ and the inequality holds. Otherwise, let \begin{align*} Q: \{0,1,\dots,r\} &\to V \end{align*} be a shortest directed path in $G_{k+1}$ from $s$ to $x$, so $Q(0)=s$, $Q(r)=x$, and $r=d_{k+1}(x)$. Suppose, for contradiction, that some vertex on $Q$ has smaller new distance than old distance. Let $j\in\{0,\dots,r\}$ be the smallest index such that \begin{align*} d_{k+1}(Q(j))<d_k(Q(j)). \end{align*} Since $Q(0)=s$ and $d_{k+1}(s)=d_k(s)=0$, we have $j\geq 1$. Put $a=Q(j-1)$ and $b=Q(j)$. By minimality of $j$, \begin{align*} d_k(a)\leq d_{k+1}(a)=j-1. \end{align*} The arc $(a,b)$ belongs to $A_{k+1}$. If $(a,b)\in A_k$, then a shortest path from $s$ to $a$ in $G_k$ followed by $(a,b)$ gives \begin{align*} d_k(b)\leq d_k(a)+1\leq j=d_{k+1}(b), \end{align*} contradicting the choice of $b$. Therefore $(a,b)\notin A_k$. Since $(a,b)$ appears in $G_{k+1}$ but not in $G_k$, it must have been created as the reverse of an arc $(b,a)$ used on the augmenting path $P_k$. Because $P_k$ is a shortest $s$-$t$ path in $G_k$, every prefix of $P_k$ is also a shortest path to its endpoint; otherwise replacing that prefix by a shorter path would produce a shorter $s$-$t$ path. Since $(b,a)$ occurs on $P_k$, the predecessor relation along $P_k$ gives \begin{align*} d_k(a)=d_k(b)+1. \end{align*} Combining this with $d_k(a)\leq j-1$ yields \begin{align*} d_k(b)\leq j-2<j=d_{k+1}(b), \end{align*} again contradicting $d_{k+1}(b)<d_k(b)$. Hence no such vertex exists, and $d_{k+1}(x)\geq d_k(x)$ for all $x\in V$. [guided] The point of this step is to control how the residual graph changes. An augmentation can delete saturated residual arcs and can create reverse residual arcs, so it is not immediate that shortest paths from $s$ cannot become shorter. We prove exactly that. Fix an augmentation index $k$. For each vertex $x\in V$, $d_k(x)$ is the shortest number of residual arcs needed to reach $x$ from $s$ before the augmentation, and $d_{k+1}(x)$ is the corresponding distance after the augmentation. We prove \begin{align*} d_{k+1}(x)\geq d_k(x). \end{align*} If $x$ is not reachable from $s$ in $G_{k+1}$, then $d_{k+1}(x)=\infty$, so the inequality holds. Otherwise, choose a shortest path \begin{align*} Q:\{0,1,\dots,r\}\to V \end{align*} from $s$ to $x$ in $G_{k+1}$, where $Q(0)=s$, $Q(r)=x$, and $r=d_{k+1}(x)$. Assume toward a contradiction that some vertex on this path became closer to $s$. Let $j$ be the first index on $Q$ for which \begin{align*} d_{k+1}(Q(j))<d_k(Q(j)). \end{align*} This first index is not $0$, because $Q(0)=s$ and the distance from $s$ to itself is always $0$. Define $a=Q(j-1)$ and $b=Q(j)$. Since $a$ occurs just before the first vertex whose distance allegedly decreased, its old distance did not exceed its new distance: \begin{align*} d_k(a)\leq d_{k+1}(a)=j-1. \end{align*} Now inspect the residual arc $(a,b)$ used by $Q$. If this arc already existed before the augmentation, namely if $(a,b)\in A_k$, then in $G_k$ we could take a shortest path from $s$ to $a$ and then traverse $(a,b)$. This gives \begin{align*} d_k(b)\leq d_k(a)+1\leq j=d_{k+1}(b), \end{align*} which contradicts the assumption that $b$ became closer. Therefore $(a,b)$ is a genuinely new residual arc. The only way a residual arc appears after augmenting is that the algorithm sent positive additional flow through the opposite residual arc. Hence $(b,a)$ lay on the chosen augmenting path $P_k$ in $G_k$. Since Edmonds-Karp chose $P_k$ to be a shortest path from $s$ to $t$, every prefix of $P_k$ must also be shortest to its endpoint; if a prefix could be shortened, replacing it would shorten the whole $s$-$t$ path. Thus the vertices along $P_k$ occur in increasing distance from $s$. In particular, if $(b,a)$ is an arc of $P_k$, then \begin{align*} d_k(a)=d_k(b)+1. \end{align*} Together with $d_k(a)\leq j-1$, this implies \begin{align*} d_k(b)\leq j-2<j=d_{k+1}(b), \end{align*} which again contradicts the assumption that $d_{k+1}(b)<d_k(b)$. Both possibilities for $(a,b)$ lead to contradictions, so every residual shortest-path distance from $s$ is nondecreasing. [/guided] [/step] [step:Show that a repeated critical residual direction forces a distance increase of at least two] Call a residual arc direction $\alpha=(u,v)$ critical at augmentation $k$ if $\alpha$ lies on the selected shortest augmenting path $P_k$ and the bottleneck residual capacity of $P_k$ equals the residual capacity of $\alpha$. Then $\alpha$ is saturated by the augmentation and therefore is not present in $A_{k+1}$. Fix a residual arc direction $\alpha=(e,u,v)$ associated to some original edge $e$. Suppose $\alpha$ is critical at augmentation $k$ and later critical again at augmentation $\ell>k$. Since $\alpha$ disappeared after augmentation $k$, it must reappear before augmentation $\ell$. The only way $\alpha=(e,u,v)$ can reappear is that, at some intermediate augmentation, positive flow is sent along the reverse residual direction $(e,v,u)$. Thus, for some index $q$ with $k<q<\ell$, the reverse direction $(e,v,u)$ lies on the shortest augmenting path $P_q$. Because $\alpha=(u,v)$ lies on the shortest path $P_k$, and every prefix of a shortest path is shortest to its endpoint, we have \begin{align*} d_k(v)=d_k(u)+1. \end{align*} Because $(v,u)$ lies on the shortest path $P_q$, and the same prefix-shortest property applies to $P_q$, we have \begin{align*} d_q(u)=d_q(v)+1. \end{align*} By distance monotonicity applied to $v$ between augmentations $k$ and $q$, \begin{align*} d_q(v)\geq d_k(v). \end{align*} Therefore \begin{align*} d_q(u)=d_q(v)+1\geq d_k(v)+1=d_k(u)+2. \end{align*} Applying distance monotonicity again between augmentations $q$ and $\ell$ gives \begin{align*} d_\ell(u)\geq d_q(u)\geq d_k(u)+2. \end{align*} Thus every time the same residual arc direction becomes critical again, the shortest-path distance from $s$ to its tail has increased by at least $2$. [/step] [step:Count critical events and augmentations] Whenever Edmonds-Karp performs an augmentation, the chosen path $P_k$ has a positive bottleneck residual capacity. At least one residual arc direction on $P_k$ attains this bottleneck, so at least one residual arc direction is critical at augmentation $k$. Fix a residual arc direction $\alpha=(e,u,v)$. Whenever $\alpha$ is critical, its tail distance $d_k(u)$ is finite, because $u$ lies on the selected augmenting path. A shortest directed path may be chosen simple: if a shortest path repeated a vertex, deleting the directed cycle between the two occurrences would produce a strictly shorter directed path with the same endpoints. Therefore the selected shortest $s$-$t$ path has at most $n-1$ arcs. Since $u$ is the tail of an arc on that path, $u\neq t$, so $u$ occurs no later than the penultimate vertex of the path. Hence \begin{align*} 0\leq d_k(u)\leq n-2. \end{align*} By the previous step, repeated criticality of the same direction raises this finite distance by at least $2$. Therefore $\alpha$ can be critical at most \begin{align*} 1+\left\lfloor \frac{n-2}{2}\right\rfloor \leq n \end{align*} times. There are at most $2m$ residual arc directions associated to the $m$ original directed edges. Hence the total number of critical events is at most $2mn$. Since every augmentation produces at least one critical event, the number of augmentations is at most $2mn$, which is $O(nm)$. [/step] [step:Multiply the augmentation bound by the breadth-first search cost] In an adjacency-list implementation of the residual graph, breadth-first search computes a shortest augmenting path in time $O(|A_k|)$. Since $|A_k|\leq 2m$ for every residual graph $G_k$, each Edmonds-Karp iteration costs $O(m)$ time to find the path and determine its bottleneck. The number of augmenting iterations is $O(nm)$ by the previous step. After the last augmentation, one additional breadth-first search certifies that no $s$-$t$ residual path remains; this adds one more $O(m)$ search. Multiplying these bounds gives total running time \begin{align*} O(nm)\cdot O(m)+O(m)=O(nm^2). \end{align*} This proves both the augmentation bound and the stated polynomial running-time bound. [/step]