Ford–Fulkerson算法铁路运输系统中车辆流问题的研究(5)
图 2.3 网络的最大流
开始给 标上 ，然后检查 ，对于 、 ，均不满足标号条件。标号无法进行下去，算法结束。
这时的可行流即为最大流 。
同时也可以找到最小割集 ，其中 为标号点集合， 为未标号点集合。弧集合 即为最小割集，其容量 。
2.5 小结
Ford-Fulkerson算法是被广泛使用的一种经典算法，其优点是实现非常简单。而其缺点则是，如果增广路选择不恰当，其复杂度会变得很大。它的复杂度不仅依赖于网络容量的规模（顶点数和弧数），还和各条弧的容量有关。因此，大量学者对此算法进行了改进或在此基础上提出了新的算法。其中，最短增广路算法（Edmonds–Karp算法[4]）和连续最短增广路算法（Dinic 算法）就是利用增广路的思想，但它们都是在分层网络（layered network）中寻找增广路进行增广[4]，而不是在容量网络中直接寻找增广路进行增广，这样使效率得到了很大的提高。
虽然理论上Ford-Fulkerson算法跟其他算法相比，效率不是很高。但是其实现非常简单，且在网络的顶点数和弧数不多，弧的容量不是很大的情况下，尤其是在弧的容量为正整数情况下，Ford-Fulkerson算法实际上跟其他算法的效率相差并不是很大。
三 最大流在交通运输系统中的应用
最大流问题是网络流问题的一个重要的内容，研究最大流问题并将其应用到工业、工程、商业、农业、运输业等领域可给我们的生活带来很大方便。但在很多情况下，实际遇到的问题可能是很复杂的，甚至是无从下手的，不过可以通过分析和简化来建立网络流模型。如果可以建立一个网络图模型，并将其转化成为最大流问题，就会找到相应的解决方法。
在当今社会生活中，所面临的问题之一就是交通运输系统客运拥挤[12]的问题，尤其是一些大城市的春运期间这种问题尤为突出。在交通运输系统中，考虑资源（列车班次、载客量或者通行速度等）的情况下，如何通过调度来实现运输能力的最大化等问题就变得非常重要[5]。这就可以转化为有关求解最大流问题。
本章首先使用C++实现寻求最大流的标号法，然后讨论一个上海市地铁客流量的问题，最后着重讨论的是我国铁路营业网络的部分线路的车辆流问题，即由京广线、京九线、浙赣线、京沪线以及陇海线等几条主干线的整条或部分线路所组成的铁路运输干线网络。
3.1 寻求最大流的标号法的C++实现
算法实现中，我们假设数据采用如下的格式进行输入：首先输入顶点数n和弧数m，然后输入每条弧的数据。规定源点为第0个顶点，收点为第n-1个顶点。每一条弧的数据的格式为：i j c f，分别表示这条弧的起点、终点、容量和流量。若没有给出初始的可行流，则取零流，即每条弧的流量f均为0。
在程序中，我们定义了一个类Network来表示网络，如下图3.1所示。关于类Network的说明如下[7][8]：
1、n为顶点数，m为弧数，MaxFlow为最大流的值，初始化时设为0；
2、以邻接矩阵Edge[MAXN][MAXN]存储容量网络，但邻接矩阵的元素是结构体Arc类型的变量，且其可存储的网络的最大顶点数为MAXN=64。Arc类型的结构体描述了网络中弧的结构，包含容量c和流量f两个成员。
3、在类Network中定义了三个数组：flag[MAXN]、prev[MAXN]、theta[MAXN]，其中：
（1）flag数组表示顶点的状态，其元素取值及含义为：-1——表示未标号，0——表示已标号但未检查，1——表示已标号且已检查；
（2）prev数组表示标号的第一个分量：指明标号从哪个顶点得到，以便调整过程中找出可改进量；