例题最大流的标号法

最大流量问题（1）流量问题是一类应用极为广泛的问题，例如在交通网络中有人流、车流、货物流，供水网络中有水流，金融系统中现金流，等等。

最大流量问题，是一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。

求最大流量的标号算法最早由福特(Ford)和福克逊(Fulkerson)于1956年提出，他们建立的“网络流理论”，是网络应用的重要组成成分。

我们今天介绍最简单的最大流量问题：找出从单个源点到单个目标点之间可以通过的最大流量。

让我们用一张图片来解释。

在上图中，圆圈表示节点，节点之间有带箭头的有向边连接，箭头方向表示从某个节点有通路到底另一个节点。

而有向边的绿色数字，表示从节点到达下一个节点的最大流量。

例如0->1的有向边的数字16表示从节点0到节点1，最大允许的流量为16（可以把流量想象为高速公路的运输能力，或者自来水管的最大出水量）。

而节点1和节点2之间有两条有向边，一条从1->2, 标记有数字10，表示经过这条边，从1到2的最大流量是10；而另一条从2->1，标记有数字4，表示经过这条边，从2到1的最大流量是4。

而红色的0表示源点，红色的5表示目标点。

现在问题来了，从单个源点0到单个目标点5之间可以通过的最大流量是多少？你能回答这个问题吗？答案是23（请你想想为什么？）。

具体的分流的情况如下图所示，其中的粉色数字表示两点之间的实际流量，它必须不大于原来规定的最大流量。

朴素贪婪算法我们先尝试采用朴素的贪婪算法来解决最大流量问题。

从假设每条边的流量都是0开始，采用贪婪算法，逐步增加对应的流量。

也就是从源点s到目标点t的某个路径上逐步增加更多流量（当然必须满足每条边的流量不超过运行的最大流量）。

假设在例子中：E是边的集合f(e)是边对应的流量C(e)是边对应的最大流量s-t路径表示从源点到目标点存在的路径算法的描述如下：1) max_flow = 02) 当存在s-t路径时，对每一条路径重复下面的步骤：a) 采用DFS（深度优先）或BFS（宽度优先）找到从s-t的路径P，并且路径上的每一条边e 都满足 f(e) < C(e)b) 如果找不到路径, 返回 max_flow。

例题最大流的标号法精品文档例题最大流的标号法例2用标号法求下图所示的公路交通网络的最大流量 (要求写出标号过程并说明得到的的确是最大流)，其中，弧旁的数字是(c「f Q。

.⑴首先,给V s标上(0, )(2)检查V s，给V s为起点的未饱和弧的未标号的终点V2标号(V s, l(V2)),其中l(V2)min [l(V s),C s2 f s2】min[ ,15 7] 8其它点不符合标号条件。

⑶检查V2，给V2为终点的非零流弧的未标号的起点V3标号(V2, |(V3)),其中l(V3)min[g), f32】min[ 8,4] 4其它点不符合标号条件。

(4)检查v3，给v3为起点的未饱和弧的未标号的终点v4、v6标号(V4, l (V4)) > ( v6,l(V6))其中，l(V4)min[?3)234 ￡34] min[4,5 4] 1l(V6)min [l(V3),C36 f36] min [4,5 1] 4其它点不符合标号条件。

⑸检查v6，给v6为起点的未饱和弧的未标号的终点v t标号(v t, l (v t))其中，l(V t) mi n[l(V6), C6t f&] mi n[4,10 5] 4其它点不符合标号条件。

由于V t已标号，反向搜索可得增广链{(V s,V2),(V3,V2),(V3,V6),(V6,Vj}，在该增广链的前相弧(v s, v2), (v3, v6), (v6,v t)上增加l (v t) 4，在后向弧(v3, v2)上减去精品文档l(V t) 4，其它弧上的流量不变，则可得一流量v(f ) 20的新的可行流如下图重新开始标号：⑹首先,给V s标上(0, )(7)检查V s，给V s为起点的未饱和弧的未标号的终点V2标号(V s, l(V2)),其中l(V2) min [l(V s),C s2 f s2】 min[ ,15 11] 4其它点不符合标号条件。

最大流问题标号法例题详解最大流问题标号法例题详解本文以一道标号法求解最大流问题的例题胶加以详细讲解，帮助读者了解其原理及运算步骤。

题目如下：给定一个网络结构如下：s (源点) 0----1----2----3----4---- t (汇点)a 25 10 12 15 20其中 s 是源点，t是汇点，aij（i,j=0,1,2,3,4)是每条弧的容量，求整个网络的最大流量。

解：1、设置标号：在最大流问题中，为了求解最大流，最常用的方法是标号法。

首先，要设置各结点标号，因为本题中有5个结点，s源点的标号为0，t汇点标号为4，其他结点即1，2，3依次标号，标号的设定不仅便于求解，而且可以在初始化的时候使用。

2、初始化标号：初始化标号即将各结点初始化为两个空集合{}，即各结点的访问和未访问标号都是空集合，即无访问的结点标号为{}，访问过的结点标号也为{}。

3、依据标号法，从源点(s=0)计算，得出每条弧的剩余容量Cij，具体推导如下：源点0 1 2 3 41 0 25 10 12 152 0 0 10 7 103 0 0 0 8 104 0 0 0 0 20其中：Cij=aij-fij (i,j=0,1,2,3,4)其中，aij 为每条弧的容量，fij 为每条弧的流量，在初始情况下，fij=0，故Cij=aij。

4、找增广路径：从源点s开始，用深度优先搜索法查找从s到t的增广路径，具体步骤如下：设置一个数组P[i]用以记录路径，P[i]表示从s到i节点所经过的上一个结点，先从源点s开始，P[0]=-1，然后查找s出发可以到达的结点，若Cij>0，则有路可达，将P[j]=i（j为s出发可达的结点），接着查找j出发可以到达的结点（该结点未被访问过）若Cjk>0，则有路可达，把P[k]=j，以此类推，直到找到P[t]=-1，即从s到t 的一条增广路径找到，这条增广路径的路径上的容量称为Cmin，它是该增广路径上各结点之间的容量最小值。