本文主要介绍网络流相关的算法，包括naive算法，Ford-Fulkerson算法，Edmonds-Karp算法，Dinic's算法和最大流最小割算法等网络流算法
图论中的一类优化问题，研究的是在一个带容量限制的有向图中，如何从指定的源点到汇点传输最大流量，或在满足最大流量的前提下实现最小费用。它是解决资源分配、路径规划、匹配等实际问题的重要模型。
最大流问题
从起点s到终点t，能通过的最大容量，图中，红色标记（分子）为流量，黑色标记（分母）所能通过的最大容量。
从下图中的标注可以看出，从s到t最大流量为5，两个方面来看：
- （1）从s出发来看，红色标记相加为5
- （2）从t进入来看，红色标记相加也为5
1. naive算法
简单算法，但是不一定能得到最大流，其他算法都是基于此算法。
算法相关的过程如下：
1.1 初始化
初始状态原图和空闲量图一致，但其表示的含义不同
- 原图：权重为容量
- 空闲量图：权重为空闲量
1.2 找路径
在空闲量图中，找到从s到t的简单路径（不能有回路）
1.2.1 找第1条路径
假设找到一条路径为：s-->v2 --> v4 -- >t，如下图所示：
由于流量为2，2，3，那么其能通过的最大流量为2
由于通过的最大容量为2，故将s-->v2 --> v4 -- >t的这条路径上的空闲量权重都减去2，又s-->v2,v2-->v4的权重都为0，故没有空闲量可以流动，故可以删去，步骤如下：
1.2.2 找第2条路径
选择 s-->v1 --> v3 -- >t 这条路径，由于流量为4，2，3，那么其能通过的最大流量为2，如下图：
由于通过的最大容量为2，故将s-->v1 --> v3 -- >t 的这条路径上的空闲量权重都减去2，又v1-->v3的权重都为0，故没有空闲量可以流动，故可以删去，步骤如下：
1.2.3 找第3条路径
选择 s-->v1 --> v4 -- >t 这条路径，由于流量为2，4，1，那么其能通过的最大流量为1，如下图：
由于通过的最大容量为1，故将s-->v1 --> v4 -- >t 的这条路径上的空闲量权重都减去1，又v4-->t 的权重都为0，故没有空闲量可以流动，故可以删去，步骤如下：
根据下面这个图来看，已经没有从 s 通往 t的路径了
1.3 结果
根据公式
可得出左边的结果，其中红色标注为流量，可从两方面来分析最大流量
- （1）从s出发来看，红色标记相加为5
- （2）从t进入来看，红色标记相加也为5
1.4 naive算法缺陷
不能保证找到的是最大流
例如下面的图：
- 若选择 s -- > v1 --> v2 --> t，则选择后的最大流为1
- 若选择s -- > v1 --> t，s --> v2 --> t，则最大流为2
2. Ford-Fulkerson 算法
2.1 初始化
初始状态原图和空闲量图一致，但其表示的含义不同
-
原图：权重为容量
-
空闲量图：权重为空闲量
2.2 找路径
在空闲量图中，找到从s到t的简单路径（不能有回路）
2.2.1 找第1条路径
假设找到一条路径为：s-->v1 --> v4 -- >t，如下图所示：
由于流量为4，4，3，那么其能通过的最大流量为3
然后将剩余流量都减去3
2.2.1.1 添加反向路径
由于v4 --> t剩余流量为0，删除这条线，然后加一条反向路径，路径上的权重为最大流3，如下图所示：
2.2.2 找第2条路径
选择 s-->v1 --> v3 -- >t 这条路径，由于流量为1，2，3，那么其能通过的最大流量为1，如下图：
由于通过的最大容量为1，故将s-->v1 --> v3 -- >t 的这条路径上的空闲量权重都减去1
2.2.2.1 添加反向路径
又s-->v1的权重都为0，故没有空闲量可以流动，故可以删去，并添加一条反向路径，路径上的权重为最大流3，步骤如下：
又由于上述图中v1--> s 有两条反向路径，其权重可合并到一起，如下：
2.2.3 找第3条路径
选择 s-->v2 --> v1 -- >v1 --> t 这条路径，由于流量为2，2，3，1，2 那么其能通过的最大流量为1，如下图：
注：反向路径也可加进去
由于通过的最大容量为1，故将s-->v2 --> v1 --> v3 -- >t 的这条路径上的空闲量权重都减去1，如下：
2.2.3.1 添加反向路径
又v1-->v3的权重为0，故没有空闲量可以流动，故可以删去，并添加一条反向路径，路径上的权重为最大流1，步骤如下：
又因为t-->v3， v3 --> v1，v1 --> v4都有两条权重为1的值，故可以合并在一起，如下：
2.3 结果
又由于图中无法找到s -- > t的节点，故结束
根据公式
可得出左边的结果，其中红色标注为流量，可从两方面来分析最大流量
- （1）从s出发来看，红色标记相加为5
- （2）从t进入来看，红色标记相加也为5
2.4 Ford-Fulkerson算法缺陷
时间复杂度有时候会很高，如下图，若选择s -- > v1 -- > v2 -- > t和 s -- > v2 --> v1 -->t 这两条路径，会来回找200次
如下面图这个过程：
3. Edmonds–Karp算法
Edmonds–Karp算法是Ford-Fulkerson算法的特例。通过限定 “最短增广路径” 的选择规则，将时间复杂度从依赖最大流 f 优化为仅依赖网络拓扑（边数 m、顶点n），稳定性更强
一般步骤如下：
-
构建残量网络；将残量初始化为容量。
-
当能找到增广路径时，循环执行以下操作：
a. （在残量网络上）找到一条增广路径。
b. 找到该增广路径上的瓶颈容量 x。
c. 更新残量（残量 ← 残量 - x）。
d. 添加一条反向路径（沿该路径的所有边权重均为 x）。
4. Dinic’s算法
4.1 Level graph说明
从s出发，每次只走一步到下一层，这样一步一步添加层
原图
步骤如下：
4.1.1 第1层
s走一步可以走到 v1 和 v2，然后把他们添加到level graph中
4.1.2 第2层
v1走一步可以走到 v3 , v2走一步可以走到 v4，然后把他们添加到level graph中
4.1.3 第3层
v3走一步可以走到 t, v4走一步可以走到 t，然后把他们添加到level graph中
4.2 第1轮循环
4.2.1 初始化
首先，得到空闲量图
4.2.2 构造level图
构造level 图如下，相关步骤如上述 level graph说明
4.2.3 找到阻塞流
使用简单算法来寻找阻塞流，在level图中找到阻塞流，然后更新剩余流量图，公式为：
红色标注为阻塞量
4.2.4 构造反向路径
由于t -- > v4 和v3 -- > v1，v1 -- >s 权重变为0，得到的反向路径如下：
4.3 第2轮循环
level图不使用，重新根据下图进行构造新的level图，如下：
4.3.1 构造level图
新的level图如下：
4.3.2 找到阻塞流
使用简单算法来寻找阻塞流，在level图中找到阻塞流，然后更新剩余流量图，如下：
4.3.3 构造反向路径
对于方向相同的流量可以进行合并。
4.4 第3轮循环
由于在空闲量图中，无法找到s到t的路径，故程序结束
4.5 结果
根据下面这个图来看，可以从两个方面来分析最大流量：
- 从 s出去的两条流量相加为19，故最大流量为19
- 从 指向t的两条流量相加为19，故最大流量为19
5. 最大流最小割
将图分成两部分S和T，其中 S和T相交为0，S和T的并集为全集。
如下图所示：只要割断其中几条线S和T则不能连通，其中的最小值为最小割值。
最小割图不唯一：最大流值 == 最小割值
5.1 分割图示例
5.2 最小割图和普通图
两种对比图，左边为最小割，右边不是。
5.3 最小割图不唯一
下面这两种都是最小割图
5.4 最大流和最小割对比
左边得出的是最小割的值
右边得出的是最大流的值
