Algorithms: 网络流：EK 算法

EK 算法

EK 算法在 Residual Graph 里找增广路的时候，使用 BFS 算法求解出的增广路一定是 shortest (in terms of fewest edges).

令 EF 算法第 $i$ 次在 $G_f$ 上找到的增广路为 $f_i$ ，并且这些 $f_i$ 是最短的（经过最少的边）。记 $G_{i}$ 为 $f_i$ 对应的 residual graph， $d_i(u,v)$ 为 $G_{i}$ 上两点之间的最短距离（最小边数），那么有

\boxed{d_{i+1}(s,v)\ge d_i(s,v)}

证明

令 $s,v$ 最短路径上的点按 distance 递增排列。我们用数学归纳法证明。

当 $d_{i+1}(s,v)=0$ 时，说明 $s=v$ 两者是同一个点，因此在 $f_i$ 对应的图里， $d_i(s,v)=0\le d_{i+1}(s,v)$ .

考虑任意长度 $L\gt 0$ ，假设引理对 $\forall v, d_{i+1}(s,v)\lt L$ 成立，考察 $\forall v,d_{i+1}(s,v)=L$ ：

在 residual graph $G_{i+1}$ 上找到 $s,v$ 的最短路，令 $x$ 为 $v$ 的上一个节点，那么有 $d_{i+1}(s,x)=L-1$

所以根据假设 $d_{i}(s,x)\le L-1$ ，我们再根据这个信息，推理 $d_i(s,v)$ 。在 $G_i$ 上有两种情况

$G_i$ 中存在 $(x,v)$ 这条边
这种情况下，我们只需要走 $s\to x\to v$ ，就一定可以保证 $d_i(s,v)\le L$ ，所以 $d_i(s,v)\le d_{i+1}(s,v)$
$G_i$ 中不存在 $(x,v)$ 这条边
如果 $G_i$ 不存在这条边，但 $G_{i+1}$ 存在这条边，这就说明
- $(v,x)\in G_i$
- EK 算法找到了一条增广路， $s\to v\to x\to t$
此时，由于 EF 算法找到的总是最短路，而 $d_i(s,x)\le L-1$ 且经过 $(v,x)$ ，因此我们可以推导出

$d_i(s,v)=d_i(s,x)-1\le L-2$
所以 $d_i(s,v)\le d_{i+1}(s,v)$ 便自动成立了