Edmonds Karp - Edmonds Karp算法（最短路径增广算法）
问题
用Edmond Karp算法求网络的最大流，是单源点、单汇点，边的容量都为正整数的网络。
Ford–Fulkerson方法
Ford-Fulkerson方法是用于求解最大流的方法（并非算法），它通过寻找增广路径（Argumenting Path）来求最大流，但具体寻找的方法有多种算法实现。
网络流中边的剩余容量（Residual Capacity）是：
边的剩余容量定义了剩余网络（Residual Network），表示该网络的可用容量。
网络中的增广路径是剩余网络中的一条路径，其中是源点，是汇点，且其中每条边（两端点为）的剩余容量都满足，其中。
Ford-Fulkerson方法的主要过程如下：
初始时将网络看作一个未被使用的原始剩余网络，该网络的最大流初始化为；
尝试从当前剩余网络中找到一条增广路径，该路径经过的所有边的最小的剩余容量即为这条流可用的容量（类似木桶短板原理）。这条增广路径使最大流的值增大为
更新该路径上每条边的剩余容量（满足反对称性）
重复第步直到无法找出更多的增广路径，算法结束。为该网络的最大流；
Edmonds-Karp算法
Edmonds-Karp算法是Ford-Fulkerson方法的一种经典实现。通过BFS算法找出一条增广路径从源点到达汇点。
设表示节点到的边的容量，表示边的剩余容量，逆向指针表示BFS搜索中从节点搜索到邻节点（或者说节点是从节点来的）。按照以下步骤进行BFS搜索增广路径：
初始时设置空队列，设置任意节点的（表示BFS搜索未开始），最大流，所有边的容量与其剩余容量相等，边上的流为，将源点加入队列中并染红；
当不为空时，从中取出头节点，若则已经找到一条增广路径；若则遍历其所有邻节点找出所有的未被染红且剩余容量的邻节点（在剩余网络中进行BFS搜索），将其加入队列中，染红，并设置逆向指针。这样重复，若最终搜索到汇点则找到一条增广路径，沿着逆向指针可以得到该增广路径上的所有边；若直到队列为空也没有搜索到汇点则说明无法再找到更多的增广路径；
重复第步，每找到一条增广路径，该路径中边的最小剩余容量即为该增广路径可用的流（Dinic算法中称为阻塞流，即路径中的瓶颈）。更新该路径上所有边的剩余容量：
更新最大流
当无法找出更多增广路径时算法结束，即为该网络的最大流；
下图演示了一条增广路径的搜索过程，其中源点为汇点为：
上图中的红线是BFS搜索剩余网络中节点的顺序，蓝线是从汇点沿着逆向指针回到源点的路径。
上图是本次BFS搜索的逆向指针。可得增广路径为，其中边是剩余容量最小的边，此条增广路径可用的流为。
然后对该增广路径上的所有边更新剩余容量，下图中每条边上的数字表示边上的流为，边的容量为，剩余容量为，其中标记为红色的边的剩余容量为：
可以发现，每次找出一条增广路径后，剩余网络中至少有一条边的剩余容量变为，上图中边的剩余容量。
重复进行BFS搜索寻找增广路径，直到无法找出更多的增广路径时，算法结束。如下图所示：
该算法时间复杂度为。