Edmonds Karp - Edmonds Karp算法（最短路径增广算法）

问题

用Edmond Karp算法求网络 $G = <V,E>$ 的最大流， $G$ 是单源点、单汇点，边的容量都为正整数的网络。

Ford–Fulkerson方法

Ford-Fulkerson方法是用于求解最大流的方法（并非算法），它通过寻找增广路径（Argumenting Path）来求最大流，但具体寻找的方法有多种算法实现。

网络流中边 $e_{u,v}$ 的剩余容量（Residual Capacity）是：

c_{f} (u, v) = c (u, v) - f (u, v)

$c_f (u,v) = c(u,v) - f(u,v)$

边的剩余容量定义了剩余网络（Residual Network） $G_f = <V, E_f>$ ，表示该网络的可用容量。

网络中的增广路径是剩余网络中的一条路径 $p = [v_1, v_2, \dots, v_n]$ ，其中 $v_1$ 是源点 $s$ ， $v_n$ 是汇点 $t$ ，且其中每条边 $e_{i,j}$ （两端点为 $v_i, v_j$ ）的剩余容量都满足 $c_f(i,j) \gt 0$ ，其中 $i, j \in [1, n]$ 。

Ford-Fulkerson方法的主要过程如下：

$(1)$ 初始时将网络 $G$ 看作一个未被使用的原始剩余网络，该网络的最大流初始化为 $flow_{max} = 0$ ；

$(2)$ 尝试从当前剩余网络中找到一条增广路径，该路径经过的所有边的最小的剩余容量 $\Delta = min \{ c(i,j) - f(i,j) \}$ 即为这条流可用的容量（类似木桶短板原理）。这条增广路径使最大流的值增大为

f l o w_{m a x} = f l o w_{m a x} + Δ

$flow_{max} = flow_{max} + \Delta$

更新该路径上每条边 $e_{i,j}$ 的剩余容量（满足反对称性）

\begin{matrix} f (i, j) = f (i, j) + Δ \\ f (j, i) = f (j, i) - Δ \\ c_{f} (i, j) = c_{f} (i, j) - Δ \\ c_{f} (j, i) = c_{f} (j, i) + Δ \end{matrix}

$\begin{matrix} f(i,j) = f(i,j) + \Delta \\ f(j,i) = f(j,i) - \Delta \\ c_f(i,j) = c_f(i,j) - \Delta \\ c_f(j,i) = c_f(j,i) + \Delta \end{matrix}$

$(3)$ 重复第 $(2)$ 步直到无法找出更多的增广路径，算法结束。 $flow_{max}$ 为该网络的最大流；

Edmonds-Karp算法

Edmonds-Karp算法是Ford-Fulkerson方法的一种经典实现。通过BFS算法找出一条增广路径从源点 $s$ 到达汇点 $t$ 。

设 $c(i,j)$ 表示节点 $v_i$ 到 $v_j$ 的边 $e_{i,j}$ 的容量， $c_f(i,j)$ 表示边 $e_{i,j}$ 的剩余容量，逆向指针 $from(j) = i$ 表示BFS搜索中从节点 $v_i$ 搜索到邻节点 $v_j$ （或者说节点 $v_j$ 是从节点 $v_i$ 来的）。按照以下步骤进行BFS搜索增广路径：

$(1)$ 初始时设置空队列 $queue$ ，设置任意节点 $v_i$ 的 $from(i) = nil$ （表示BFS搜索未开始），最大流 $flow_{max} = 0$ ，所有边的容量与其剩余容量相等 $c(i,j) = c_f(i,j)$ ，边上的流为 $f(i,j) = f(j,i) = 0$ ，将源点 $s$ 加入队列中并染红；

$(2)$ 当 $queue$ 不为空时，从中取出头节点 $v_i$ ，若 $v_i = t$ 则已经找到一条增广路径；若 $v_i \neq t$ 则遍历其所有邻节点找出所有的未被染红且剩余容量 $c_f(i,j) \gt 0$ 的邻节点 $v_j$ （在剩余网络中进行BFS搜索），将其加入队列 $queue$ 中，染红，并设置逆向指针 $from(j) = i$ 。这样重复，若最终搜索到汇点 $t$ 则找到一条增广路径，沿着逆向指针可以得到该增广路径上的所有边；若直到队列 $queue$ 为空也没有搜索到汇点 $t$ 则说明无法再找到更多的增广路径；