Ford–Fulkerson算法铁路运输系统中车辆流问题的研究(6)
（3）theta数组表示标号的第二个分量：用以确定增广路的可调整量 。
4、成员函数init()用来输入数据，初始化网络及相关数据的；
图 3.1 类Network
5、成员函数label()是标号过程，检查每个顶点并将与之相邻的顶点标号，采用的是广度优先搜索的策略，因此，在程序中，定义了一个队列queue<int>q。
每一次标号过程如下：
（1）先将flag、prev、theta这3个数组的元素都初始化为-1；
（2）将源点初始化为已标号但未检查的顶点，即flag[0]=0，prev[0]=0，theta[0]=INF，INF表示无穷大（这里用INT_MAX表示，其值是最大的int型整数），并将源点入队列；
（3）当队列非空且收点未标号时，从队列头取出队列头顶点，设此顶点为v，则v肯定是已标号但未检查的顶点。因此，检查顶点v的正向和反向邻接顶点，如果未标号且当前可以标号，则对这些顶点进行标号并入队列，这些顶点都是已标号但未检查的顶点。此后顶点v为已标号且已经查的顶点。反复执行，直至队列为空或者收点已获得标号。
6、成员函数adjust()是调整过程。从收点出发，通过标号的第一个分量，即prev[n-1]，采用反向跟踪的方法，一直到源点为止，这个过程途径的顶点和弧即构成了增广路。而收点的第二个分量，即theta[n-1]，就是本次调整过程的可调整量。然后将前置弧的流量增加theta[n-1]，后置弧的流量减少theta[n-1]；
7、成员函数is_end()，判断算法是否结束。当收点未获得标号，或者收点的可调整量theta[n-1]为0，表明标号法的标号和调整过程完成，应退出循环；
8、成员函数max_flow()计算最大流的流量值；
9、成员函数print()打印最大流值及各条弧上的流量。
类Network的详细实现代码请参见附录。
而寻找最大流标号法的主程序代码如下图3.2所示。
图3.2 寻找最大流标号法的主程序[8]
3.2 地铁运输系统中客流量问题
城市公共交通问题是一个全球性的问题，而作为国际性都市的上海同样面临着这样的问题。上海是我国最繁华的城市之一，同时也是交通最繁忙的城市之一，其地铁目前运营线路总里程已经达到473公里（不含磁悬浮示范线），位居世界第一，客运量日均突破了七百万人次，工作日早高峰部分线路和区段出现大客流拥挤、满载率居高不下的情况，只能通过限流来控制单位时间内的客流量。鉴于其客流量大且多节点多线路换乘的复杂性，我们以上海市地铁为例，看看是如何分配客流量，以使其在有限的运输能力下的载客量达到最大的。
图3.3 上海地铁线路图（部分）
考虑上海地铁运输系统工作日早高峰时段从上海体育馆站到世纪大道站的客流量问题，主要包括1号线上海体育馆至人民广场段，4号线上海体育馆至世纪大道段，9号线徐家汇至至世纪大道段，10号线常熟路至南京东路段，2号线人民广场至世纪大道段。这几段包括了上海市最繁忙拥挤的几条地铁线路。建立网络流模型如下图3.4所示，图中的载客容量（单位：千人次）的数据是根据网上查询的上海市地铁各线路客流量统计数据整理而成。
图3.4 上海体育馆站到世纪大道站的线路图
：上海体育馆， ：徐家汇， ：常熟路， ：西藏南路， ：陆家浜路， ：老西门， ：人民广场， ：南京东路， ：世纪大道
输入各顶点以及弧的容量如图3.5所示，运行输出结果如图3.6所示，即每天早高峰时段（早上7:30 - 9:30）从上海体育馆站到世纪大道站的最大客流量为13.5万人次。