图网络—寻找网络最大流算法(1)-一一网

这是我参与8月更文挑战的第15天，活动详情查看：8月更文挑战

最大流问题(Maximum Flow Problem),属于图论的范畴，在最大流问题中我们研究的图是有向有权图，也就是边都是有方向和权重的。图中有很多结点。

起始结点用 s 表示(source)
终点用 t 来表示(target)

可以形象地理解最大流问题，也就是我们想要把水从起点 s 输送到终点 t 问题来解释一下最大流问题，中间结点连接的边(管道)都有一定的承载能力，这里就是容量概念(capacity) 。容量或者说管道承载能力可以理解为每秒可以通过管道的水的量，图中能够从起点到终点输送所少立方米的水。这就是最大流问题。那么对于最大流问题，我们需要有哪些信息，这些信息又都代表什么样含义。

首先需要有一个由结点和结点间的边所组成有有向有权图，然后需要支持图中最大流的起点和终点，我们要做的就是找到一些合理路径让从起点到终点单位时间流量最大。也就是在当前网络下，最多可以从起点输送到终点多少量的水。

如上图边权重可以理解为水管的容量，这里连接 v1 和 v3 的边的权重为 2，表示水管承载能力为 2 ，开始之前我们还需要介绍一个概念就是空闲量(residual)，也就是管道承载的容量(capacity)减去实际流量(flow)的量，也就是该水管承载能力还有多少没用上。
最开始没有任何流量经过网络时，图中没有流量时，这时空闲量就等于水管承载容量，下面列出两张图便于大家观察，左边是原图，而右边表示水管空闲量图。

如下图，接下来一系列操作都是表示空闲量图(residual graph)图上进行操作。首先我们图找到一条从起点到终点的简单路径，所谓简单路径也就是该路径中不能存在回路。寻找简单路径方法很多，其中我们先将图看成无权图，然后找到最短路径做为该图的简单路径。接下来我们就找到了一条路径，然后带有颜色线标准这条路径如下图(左侧)。这条路径从起点 s 途径 v2 , v4 最终流到终点。路径上边权重分别是 2，2，3，其中最小权重为 2 ，由于短板效应所有这条路径最多只能通过 2 份的水，我们 2 份水通过这条路径，所以路径上变得空闲量都会分别减去 2 而变成 0， 0， 1 如下右图，现在我们就将空闲量图进行进行了一次更新。

通过观察我发现 s 到 v2 和 v2 到 v4 间两条边空闲量为 0 表示他们已经包含不允许水从这两个管道流通，所以我们就可以把这两条边从空闲图中去掉如下左图。到此就完成第一轮循环。接下来就是重复上述步骤，在空闲图中再找到一条简单路径 s v1 v3 t ，因为这条路径上最小权重等于 2 所以将所有空闲量都减去 2 ，发现v1 到 v3 的空闲量在减去 2 后变为 0，那么就去掉他们之间边，从而空闲图经过第二次迭代就变为下右图。

继续进入下一个循环，这次我就不解释，想必大家看图就了解这些图是如何得到了吧，如果还是不明白这两图是怎么来的可以评论区给我留言。

现在我们在看上一次循环后得到右下图，在这张图我们已经找不到任何路径让水从起点流到终点。当不能在空闲图中找到从起点到终点路径，我们就可以退出循环。

现在我们就有一个循环得到空闲图(residual graph)，我们流量等于容量减去空闲量就可以计算网络中的流量 Flow = Capacity – Residual

通过这个公式我们就可以计算出下左图，其中 2/2 表示 flow/capacity 也就是容量为 2 水管通过 2 流量，空闲量为 0。

通过上左图不难看出网络的总流量为 5 ，那么这里网络流量为 5 如何计算的，从起点 3 流出的流量为 2 + 3 所以网络最大流量为 5。

不过接下来我们来看这种算法的问题，这种算法问题就是无法保证找到解是最大流，通过一个例子来解释这个问题。我们还是对上面的例子进行分析。算法能够找到最大流取决查找路径的先后顺序。如果在一次循环找到，找到 s v1 v4 t 这条路径，还是采用已经介绍的算法得到了更新后空闲量图，如右下图。

然后继续在上面得到空闲图找到另一条路径 s v1 v3 t 然后继续更新空闲量图得到下右图，然后我们再来观察一下得到空闲图，发下这个空闲图(下右图)已经无法再找到从起点流到终点的路径，而从得到结果的空闲图。

好我们在用原图的容量减去得到空闲图中的空闲量就得到下左图这样，通过计算从起点流出流量发现通过上面计算得到该图最大流量为 4 小于上一次得到 5 那么这个结果显然不是这张图最大流量。

通过上面例子我们就解释通过这种简单方法因为选择路径顺序不同，可能找到网络流并不是最大网络流。这里不是最大流，其实有关上面图找到流量图有一个名字叫 blocking flow，为什么叫做阻塞流，其实就是表示有了这个流量，网络就是无法再由流量从起点流向终点。当然最大流也是一种阻塞流，显然当最大流时，网络无法通过更多流量。