本文将精炼地总结出网络流的基础知识，并对几种最大流算法进行比较分析，适合初学者阅读。
基本概念
什么是网络流（最大流）
网络流有以下要素：
- 有向图
- 两个特殊点：源点（S）、汇点（T）
- 边的权值代表这条路的容量
知道这三个概念之后，最大流就很容易理解了，顾名思义：如果把图比作水流的话，就是从起点（S）到终点（T）的最大水流量。
性质
- 容量限制（Capacity Constraints）：一条边的流量不能超过它的容量（显而易见）
- 斜对称（Skew Symmetry）：由u到v的净流必须是由v到u的净流的相反
- 流守恒（Flow Conservation）：除了S和T两点外，所有点的流入量之和等于流出量之和
如上图所示，斜杠左面代表当前流量，右边代表容量。
最大流算法
首先，我们来思考一种求最大流的方法：
每次用dfs从源到汇找一条可行路径， 然后把这条路塞满。这条路径上容量最小的那条边的容量，就是这次dfs所找到的流量。然后对于路径上的每条边，其容量要减去刚才找到的流量。这样，每次dfs都可能增大流量，直到某次dfs找不到可行路径为止，最大流就求出来了。
这个想法是否正确？
以这个图为例：
如果第一次dfs的路径是s –> a –> b –> t，那么我们会得到一个100的流。然后更新这三条边的容量，再也没有新的路径了，也就是说这样求出的最大流是100。
然而实际上此图存在流量为200的流：s –> a –> t， s –> b –> t。
问题原因在于：过早的占用a –> b 通道。
一个改进的方法：修改已建立的网络，使“不合理”的流量被修正。
实现方法：对上次dfs时找到的流量路径上的边，添加一条“反向”边，反向边上的容量等于上次dfs时找到的该边上的流量，然后再利用“反向”的容量和其他边上剩余的容量寻找路径。
如：
第一次dfs：
第一次dfs后，添加反向边：
这样第二次dfs时就可以在新的网络里找到新路径。
第二次dfs搜索又找到了一个流量为100的流，加上第一次搜索得到的流量为100的流，总流量上升到200。
第二次dfs后再添加反向边
此图已经无法dfs，所以最大流就是200。
Ford-Fulkerson算法（增广路方法 简称FF方法）
残余网络（residual network）
在一个网络流图上，找到一条源到汇的路径（即找到了一个流量）后，对路径上所有的边，其容量都减去此次找到的流量（剩下称之为剩余容量），对路径上所有的边，都添加一条反向边，其容量也等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”。
内容
求最大流的过程，就是不断找到一条源到汇的路径，然后构建残余网络，再在残余网络上寻找新的路径，使总流量增加，然后形成新的残余网络，再寻找新路径…..直到某个残余网络上找不到从源到汇的路径为止，最大流就算出来了。
增广路径（augmenting path）
每次寻找新流量并构造新残余网络的过程，就叫做寻找流量的“增广路径”，也叫“增广”。
为什么添加反向边是有效的？
假设在第一次寻找流的时候，发现在 b->a 上可以有流量n来自源，经过b，再流到a后抵达汇点。
构建残余网络时添加反向边a -> b，容量是n。增广的时候发现了流量n-k，即新增了n-k的流量。这n-k的流量，从a进， b出，最终流到汇。
现要证明这2n-k的流量，在原图上确实是可以从源流到汇的。
首先把a和b的输入输出合并如下：
在原图上可以如下分配流量，说明能有2n-k从源流到汇点：
时间复杂度
假设每条边的容量都是整数，这个算法每次都能将流至少增加1。
整个网络的流量最多不超过所有的边的容量和V，找增广路径的算法可以用dfs， 复杂度为边数m+顶点数n，dfs 最多运行V次。
所以时间复杂度为 V*(m+n) 。
如图，至少两次就可以得到最大流，然后最坏情况可能需要200次。
如何避免这种情况的发生？
Edmonds-Karp算法（最短路径增广算法 简称EK算法）
Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的 Dinic 算法都属于此。
在每次增广的时候，选择从源到汇的具有最少边数的增广路径，即不是通过dfs寻找增广路径，而是通过bfs寻找增广路径。
时间复杂度
已被证明这种算法时间复杂度是： nm^2 (n是点数， m是边数）
The running time of O(V E2) is found by showing that each augmenting path can be found in O(E) time, that every time at least one of the E edges becomes saturated (an edge which has the maximum possible flow), that the distance from the saturated edge to the source along the augmenting path must be longer than last time it was saturated, and that the length is at most V. (via WIKIPEDIA)
前面的网络流算法，每进行一次增广，都要做一遍BFS，十分浪费。能否少做几次BFS?
Dinic算法
先利用 BFS对残余网络分层，一个节点的“层”数，就是源点到它最少要经过的边数。 分完层后，利用DFS从前一层向后一层反复寻找增广路（即要求DFS的每一步都必须要走到下一层的
节点）。
DFS过程中，要是碰到了汇点，则说明找到了一条增广路径。此时要增加总流量的值，消减路径上各边的容量，并添加反向边，即所谓的进行增广。
DFS找到一条增广路径后，并不立即结束，而是回溯后继续DFS寻找下一个增广路径。
回溯到哪个节点呢？
回溯到的节点u满足以下条件：
- DFS搜索树的树边(u,v)上的容量已经变成0。即刚刚找到的增广路径上所增加的流量，等于(u,v)本次增广前的容量 (DFS的过程中，是从u走到更下层的v的)。
- u是满足上述条件的最上层的节点
如果回溯到源点而且无法继续往下走了， DFS结束。
因此，一次DFS过程中，可以找到多条增广路径。
DFS结束后，对残余网络再次进行分层，然后再进行DFS当残余网络的分层操作无法算出汇点的层次（即BFS到达不了汇点）时，算法结束，最大流求出。
一般用栈实现DFS,这样就能从栈中提取出增广路径。
时间复杂度
Dinic 复杂度是 n*n*m (n是点数， m是边数）
因为在Dinic的执行过程中，每次重新分层，汇点所在的层次是严格递增的，而n个点的层次图最多有n层，所以最多重新分层n次。在同一个层次图中，因为每条增广路都有一个瓶颈，而两次增广的瓶颈不可能相同，所以增广路最多m条。搜索每一条增广路时，前进和回溯都最多n次，所以这两者造成的时间复杂度是O(nm)；而沿着同一条边(i,j)不可能枚举两次，因为第一次枚举时要么这条边的容量已经用尽，要么点j到汇不存在通路从而可将其从这一层次图中删除。综上所述，Dinic算法时间复杂度的理论上界是O(n^2*m)。 （via 百度百科）
Improved SAP 算法
SAP 类算法在寻找增广路时总要先进行 BFS，BFS 的最坏情况下复杂度为 O(E)，这样使得普通 SAP 类算法最坏情况下时间复杂度达到了 O(VE2)。
为了避免这种情况，Ahuja 和 Orlin 在1987年提出了Improved SAP 算法，它充分利用了距离标号的作用，每次发现顶点无出弧时不是像 Dinic 算法那样到最后进行 BFS，而是就地对顶点距离重标号，这样相当于在遍历的同时顺便构建了新的分层网络，每轮寻找之间不必再插入全图的 BFS 操作，极大提高了运行效率。
国内一般把这个算法称为 SAP…显然这是不准确的，毕竟从字面意思上来看 E-K 和 Dinic 都属于 SAP，我们还是习惯称为 ISAP 或改进的 SAP 算法。
与 Dinic 算法不同，ISAP 中的距离标号是每个顶点到达终点 t 的距离。同样也不需显式构造分层网络，只要保存每个顶点的距离标号即可。程序开始时用一个反向 BFS 初始化所有顶点的距离标号，之后从源点开始，进行如下三种操作：
- 当前顶点 i 为终点时增广
- 当前顶点有满足 dist[i] = dist[j] + 1 的出弧时前进
- 当前顶点无满足条件的出弧时重标号并回退一步。
整个循环当源点 s 的距离标号 dist[s] >= n 时结束。
对 i 点的重标号操作可概括为 dist[i] = 1 + min{dist[j] : (i,j)属于残量网络Gf}。
时间复杂度
虽然 ISAP 算法时间复杂度与 Dinic 相同都是 O(V2E)，但在实际表现中要好得多。
要提的一点是关于 ISAP 的一个所谓 GAP 优化。
由于从 s 到 t 的一条最短路径的顶点距离标号单调递减，且相邻顶点标号差严格等于1，因此可以预见如果在当前网络中距离标号为 k (0 <= k < n) 的顶点数为 0，那么可以知道一定不存在一条从 s 到 t 的增广路径，此时可直接跳出主循环。
在实测中，这个优化是绝对不能少的，一方面可以提高速度，另外可增强 ISAP 算法时间上的稳定性，不然某些情况下 ISAP 会出奇的费时，而且大大慢于 Dinic 算法。相对的，初始的一遍 BFS 却是可有可无，因为 ISAP 可在循环中自动建立起分层网络。实测加不加 BFS 运行时间差只有 5% 左右，代码量可节省 15~20 行。
总结
Topcoder上有人对几种算法做了性能测试：
稀疏图：
中等稠密图：
稠密图：
显而易见，ISAP在各种情况的表现都是最优。
总之，在信息学竞赛中，网络流问题往往难点不在算法，而在建模。
最后推荐两篇文章，写的比较好：