网络流算法

网络流算法

图论中的一类优化问题，研究的是在一个带容量限制的有向图中，如何从指定的源点到汇点传输最大流量，或在满足最大流量的前提下实现最小费用。它是解决资源分配、路径规划、匹配等实际问题的重要模型。

最大流问题

从起点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），稳定性更强

一般步骤如下：

1. 构建残量网络；将残量初始化为容量。

2. 当能找到增广路径时，循环执行以下操作：

   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 最大流和最小割对比

左边得出的是最小割的值

右边得出的是最大流的值