目录
第一章 绪论 ................................................................................................................. 1
1.1 最大流问题的研究内容及背景 .................................................................... 1 1.2 最大流问题的发展状况 ................................................................................. 1 1.3 选题的意义 ........................................................................................................ 2
第二章 预备知识 ....................................................................................................... 4
2.1 图论 ...................................................................................................................... 4 2.2 网络的基本概念 ............................................................................................... 5 2.3 最大流问题核心依据——Ford-Fulkerson最大流最小割定理 ......... 7
第三章 最大流问题的几种算法 .................................................................... 9
3.1 标号法(Ford-Fulkerson算法) ...................................................................... 9 3.2 Edmonds-Karp修正算法 ........................................................................... 12 3.3 Dinic算法 ...................................................................................................... 15
第四章 最大流问题的应用 ............................................................................. 19
4.1 铁路货运列车的最优调度 ........................................................................... 19
第五章 结论 ............................................................................................................. 30 参 考 文 献 ............................................................................................................... 31 致谢辞 ............................................................................................................................. 32 附录1英文原文 ....................................................................................................... 33 附录2中文译文 ....................................................................................................... 37
山东科技大学本科毕业设计（论文）
第一章 绪论
1.1 最大流问题的研究内容及背景
最大流问题也就是是指网络分析问题的一类，它是在指定的条件下,要求通过网络的物流、能量流、信息流等流量为最大的问题。比如交通运输网络中的人流、车流、物流,供水网络中的水流、金融系统中的现金流通信系统中的信息流等等，都属于最大流问题。
图论是组合数 学的—个分支与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系而且其应用十分广泛，是近年来较为活跃的数学分支之一。它的产生和 发展历经了二百多年的历史，瑞士数学家欧拉(L．Euler)在1736年解决了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人。早期的图论与数学游戏有密切的联系，如哈密尔顿 的周游世界问题、迷宫问题、博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。20世纪后，图论的应用渗透到许多其他学科领域，如物理、化学、信息学、运筹学、博奕论、计算机网络、社会学以及集合论、矩阵论等。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之一，也成为现代研究最大流问题的一个重要工具。
1.2 最大流问题的发展状况
最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克（Hitchcock），1941年他在研究生产组织和铁路运
1
山东科技大学本科毕业设计（论文）
输方面的线性规划问题时提出运输问题的基本模 型；后来柯普曼（Koopmans）在1947年独立地提出运输问题并详细地对此问题加以讨论；从上世纪40年代早期开始，康脱洛维奇（Kantorovich）围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与 一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的发展。
最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点 为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。
最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。
1.3 选题的意义
在日常生活和生产中我们时常遇到一些网络图。如交通图、旅游线路图、管道系统图等。在优化理论 中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以及这些对象之间的相互联系。例如旅游管理、网络通信、交通运输、金融系统等问题都可以用网络图来描述。
最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点
2
山东科技大学本科毕业设计（论文）
为收点，其余的点为中间点，在所有的点 都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。
最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。
3
山东科技大学本科毕业设计（论文）
第二章 预备知识
2.1 图论
所谓“图论”，顾名思义也就是是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映一些对象之间的关系。图形中的点表示对象(如工序、选手、通讯站等)，两点之间的有向或无向连线表示对象之间具有某种特定的关系(如先后关系、胜负关系、传递关系、连接关系等)。
物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连 接起来的图进行模拟。这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的vi,vj相对位置如何，都是无关紧要的。 定义1：两点之间不带箭头的连线称为边，一条连接vi,vj的边记为vs (或
[vi,vj])，表示边的集合。
定义2：两点之间带箭头的连线称为E?{e1,e2?,em}弧，一条以vi为始点vj 为终点的弧记为ai?(vi,vj),A?{a1,a2,?am}表示弧的集合。
定义3：由点和边构成的图为无向图，记为G?(V,E)；由点和弧构成的图为有向图，记为D?(V,A).
定义4：在无向图G中，若存在一个点边交错序列
(vi1,ei1,vi2,ei2,?vik?1,eik?1,vik)，满足
4
山东科技大学本科毕业设计（论文）
eit?[vit,vit?1](t?1,2,?k?1)，则称之为一条联结vi1和vik的链，记为(vi1,vi2,?,vik),若vi1?vik，则称之为圈。
定义5：在有向图D中，若存在一个点弧交错序列
(vi1,ai1,vi2,ai2,?vik?1,aik?1)，弧ait的始点为vit，终点为vit?1，记为ait?(vit,vit?1)，则称这条点弧的交错序列为从vi1到vik的一条路，记为(vi1,vi2,?,vik)。若路的第一点和最后一点相同，则称之为回路。链与路中
的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。 定义6：如果对于一个无向图G的每一条边，相应有一个权数wij，则称这样的图为赋权图，记为G?(V,E,C)。
定义7：如果对于一个有向图D的每一条弧，相应有一个权数cij，称这样的图为网络,记为D?(V,A,C)。
一般在网络图中，每条弧的权，不是表示弧的长度、而是表示弧的宽度，即代表距离、费用、通过能力(容量)等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络（参见文献[17]）。 定义8：在图G中，若任何两个点之间至少有一条链（或一条路），则称G是连通图，否则，称为不连通图。
2.2 网络的基本概念
假设要把起点的一批流转物运送到终点去，在每一弧上通过流转物的总量不能超过这条弧上的容量，问题是应该怎样安排运送，才能使从起点
5
山东科技大学本科毕业设计（论文）
运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究内容（参见文献[15]），以下讨论的网络均为只有一个发点vs和一个收点vt的容量网络D?(V,A,C)。 定义9：对任意容量网络D?(V,A,C)中的弧(vi,vj)有流量fij，称集合
f?{fij}为网络D上的一个流，称满足下列条件的流f为可行流：
(1)容量限制条件：对D中每条弧(vi,vj)，有0?fij?cij； (2)平衡条件：
①对中间点vi，有?jfi??ikf(即中间点vi的物资的输入量与输出
jk量相等)。
②对收、发点vt,vs有?fsi??fjt?W(即从vs点发出的物资总量
ij等于vt点入的量) ，W为网络流的总流量。
在容量网络D?(V,A,C)中cij表示弧(vi,vj)的容量，令xij为通过弧
(vi,vj)的流量，显然有0?xij?cij，流{xij}应遵守点守恒规则，即：
??W?x?x??ij?ji?0??W?称为守恒方程。
定义10：对任意容量网络D?(V,A,C)，寻求一可行流f使得流量W取得 极大值，这个可行流f便称为最大流。
定义11：在容量网络D?(V,A,C)中，若?为网络中从发点vs到收点vt的一条路，给?定向为从vs到vt，?上的弧凡与?同向称为前向弧。凡与?反
6
i?si?s,t
i?t山东科技大学本科毕业设计（论文）
向称为后向弧，其集合分别用??和??表示，f是一个可行流，如果满足
???0?fij?cij(vi,vj)?? ????cij?fij?0(vi,vj)??则称?为从vs到vt的(关于f的)增广链。
定义12：在容量网络G?(V,A,C)中，若有弧集A'为A的子集，将D分为两个子图D1,D2，其顶点集合分别记S,S，SS?V,SS??，vs,vt分别
属于S,S，满足：①D(V,A?A')不连通；②A''为A'的真子集，而D(V,A?A'')仍连通，则称A'为D的割集，记A'?(S,S)。
割集(S,S)中所有始点在S，终点在S的边的容量之和，称为(S,S)的割集容量，记为C(S,S)。
2.3 最大流问题核心依据——Ford-Fulkerson最大流最小割定
理
Ford-Fulkerson最大流最小割定理是由Ford和Fulkerson在1956年提出的，是图论的核心定理。
定理1：（Ford-Fulkerson最大流最小割定理）任一容量网络D中，从vs到vt 的最大流{fij}的流量等于分离vs,vt的最小割的容量。
证明：设在D中从vs到vt的任一可行流{xij}的流量为W，最小割集为
(S,S)，最小割集的容量为C(S,S)。这个定理的证明分两步：
7
山东科技大学本科毕业设计（论文）
⑴ 我们先证明W?C(S,S)：
由守恒方程可得：
W??(?xij??xji)i?Sjj???(xij?xji)???(xij?xji)
i?Sj?Si?Sj?S???(xij?xji)i?Sj?S(3.1)因此有：W???(xij?xji)???xij???cij?C(S,S)。
i?Sj?Si?Sj?Si?Sj?S⑵ 下面我们证明一个可行流是最大流，当且仅当不存在关于它的从vs到vt的增广路径：
必然性：显然，因为如果存在增广路径，还可以继续增广，流就不是最大流。
充分性：假设可行流{xij}是一个不存在关于它的增广路径的流，对于最小割集(S,S)，有对任意i,j?S，存在从vi到vj的增广路径，而对任意
i?S,j?S，不存在从vi到vj的增广路径，由定义可知对任意i?S,j?S有：
xij?cij,xji?0
由公式(3.1)可知：W???cij?C(S,S)。
i?Sj?S即流的值等于割集的容量，定理得证。
8
山东科技大学本科毕业设计（论文）
第三章 最大流问题的几种算法
最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大流问题。下面用数学语言来说明最大流问题：
1.设有一个有向连通图G(V,A)，在V中指定一点称为发点s,和另外一点为收点t，其余的称为中间点，弧（arc）集A中每条弧（i，j）上有非负数cij称为这弧的容量，记容量集为c={cij}，称这样的图为一个网络，记为G(V,A, c)（注：当（i，j）不是弧时cij=0）。
2.在弧集A上的弧（i，j）定义一非负数fij，称为弧（i，j）上的流量，流量的集合f={fij}称为网络的一个流，满足下列条件的称为可行流：
1）容量限制条件，所有的弧的流量fij不大于弧的容量cij； 2）平衡条件，对所有的中间点，流入的流量和等于流出的流量和，发点流出的流量F等于流进收点的总流量F.
最大流问题就是求总流量最大达可行流。
求解最大流问题存在许多算法，这一节将介绍几种常用算法。
3.1 标号法(Ford-Fulkerson算法)
3.1.1标号法(Ford-Fulkerson算法)思想
Ford-Fulkerson标号法是一种找最大流f的算法。它是由Ford和Fulkerson于1957年最早提出的，其基本思想是从任意一个可行流出发寻
9
山东科技大学本科毕业设计（论文）
找—条增广路径，并在这条增广路径上增加流量，于是便得到一个新的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量……，继续这个过程，一直到找不到新的增广路径为止（参见文献[2]）。
采用Ford-Fulkerson标号法求解最大流问题时，在标号过程中，一个点仅有下列三种状态之一：标号已检查(有标号且所有相邻点都标号了)；标号未检查(有标号，但某些相邻点未标号)；未标号（参见文献[6]）。
Ford-Fulkerson标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献[18]）。现在我们考虑只有一个发点vs和一个收点vt的容量网络，应用Ford-Fulkerson标号算法求解它的最大流
3.1.2 Ford-Fulkerson标号法的具体步骤 A:标号过程
步骤0 确定一初始可行流{fij}，可以是零流。 步骤1 给发点vs以标号[?,vs]。
步骤2 选择一个已标号但未检查的点vi，并作如下检查：
① 对每一弧(vi,vj)，若vj未给标号，而且cij?fij时，即流出未饱和弧,给vj以标号[?j,vi]；
② 对每一弧(vj,vi)，若vj未给标号，而且fji?0时，即流入非零流弧，给vj以标号[?j,?vi]；
??cij?fij其中：?j?min{?i,?},?????fji10
若(vi,vj)为流出未饱和弧若(vj,vi)为流入非零流弧
山东科技大学本科毕业设计（论文）
步骤3 重复步骤2直到收点vt被标号，或不再有顶点可以标号为止。 如果点给了标号说明存在一条增广路径，故转向增广过程B。如若点vt不能获得标号，而且不存在其它可标号的顶点时，算法结束，所得到的流便是最大流。 B：增广过程
由终点vt开始，使用标号的第二个元素构造一条增广路径?(点vt的标号的第二个元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等)，在?上作调整得新的可行流
{fij}，(标号的第二个元素的正负号表示通过增加或减少弧流来增大流值)。令?为vt标号的第一个元素的值，作
?fij??(vi,vj)是?上前向弧??fij??fij??(vj,vi)是?上后向弧???fij其它
以新的可行流{fij}代替原来的可行流，去掉所有标号，转标号过程的步骤1。
采用Ford-Fulkerson标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献[14]）。
11
山东科技大学本科毕业设计（论文）
3.2 Edmonds-Karp修正算法
Ford-Fulkerson标号算法理论上存在着严重的弱点，以下图3.2.1为例各边上的权是它们的容量，其最大流流量为2m，若增广路径选择得不好,即交替地采用sabeft和sdebct作为增广路径，则每次增广只能使总的流量增加1,当初始流选为零流，无疑需作2m?1次的增加流量才能使之达到最大，可见Ford-Fulkerson算法的时间复杂度不仅依赖于网络的规模(即依赖于网络点数和边数)，还和各边的容量有关,而容量可以是任意的正整数。如图3.2.1中，当sabeft和sdebct交替作为增广路径时，be弧交替地以前向弧和后向弧出现。利用Ford-Fulkerson算法求解就很麻烦了（参见文献[8]）。
对于Ford-Fulkerson算法,由于增广路径选取的任意性造成了该算法不是好算法，Edmonds和Karp对Ford-Fulkerson算法作修正，可概括为一句话：“先给标号的先扫描”。它的意思是对已给标号的顶点v进行扫描时，先对所有和v邻接的未给标号的顶点给予标号。具体的说图3.2.1的例子，顶点s先标记，所以应该先扫描，因此避免了Ford-Fulkerson算法那样交替地出现sabeft,sdebct的情况，也就避免了be弧交替地以前向弧和后向弧来回摇摆的局面。所以Edmonds-Karp的修正实质是对顶点给标记过程采用了“宽度优先”策略。使得流量增加总是沿着一条长度最短的路径从s流向t的（参见文献[3]）。
s m m d 12 a m m b m c m 1 m e 图3.2.1 m f t 山东科技大学本科毕业设计（论文）
现在我们仍考虑只有一个发点vs和一个收点vt的网络图，Edmonds-Karp修正算法的主要步骤是： ① 确定一初始可行流{fij}，其流量W(f)。
② 检验当前所确定可行流是否是网络中的最大流，若不是，需进一步调整
(检验一个可行流是否为最大流。只要检查一下当前可行流是否还存在增广路径，若存在，则说明当前可行流还不是最大流，否则是最大流)。 ③ 将当前的可行流调整成一个流量更大的新可行流，再由②检验。
同样地，我们通常用观察法确定网络的—个初始可行流。对于较为复杂的网络，至少能把初始可行流取为零流。通过在网络上标号的方法能系统地寻找出当前可行流的增广路径，它的基本思想是：从起点vs起，逐步寻找vs至各点vi间的增广路径，若能找到vs至vi的一条增广路径，则给点vi标号[?i,?i]（其中第一个标号?i即为vs至vi这条增广路径上的最大可调整量，第二个标号?i则表示这条可行流上点vi的前一点是?i点）。根据标号可反向追踪而写出这条增广路径。在逐步扩大已标号的过程中，一旦终点vt标上号，表示已找到一条由vs至vt的增广路径。反之，如果标号过程进行至某一步中止了，而vt尚未标号，则表明对当前的可行流，网络中不存在任何增广路径。当前可行流即为最大流。Edmonds-Karp修正算法的具体步骤如下：
① 给发点vs标号[?,vs]，含义为vs至vs的增广路径已找到，前一点为vs，这条增广路径上的调整量为?。选与vs关联的从vs流出的未饱和弧
13
山东科技大学本科毕业设计（论文）
(vs,vi)或流入vs的非零流弧(vi,vs)，给vi标号[?i,vs] (对于流出弧)或
[?i,?vs] (对于流入弧)。
??csi?fsi若(vs,vi)为流出未饱和弧其中：?i??
??fsi若(vi,vs)为流入非零弧② 将顶点集分为互补的二个点集S、S，其中S为已标号点集，S为未标号点集；
③ 考虑所有这样的弧(vi,vj)或(vj,vi)，其中vi?S,vj?S。若弧(vi,vj)为从vi流出的未饱和弧，则给vj标号[?j,vi]。其中?j?min{?i,cij?fij}；若弧(vj,vi)为流入vi的非零流弧，则给vj标号[?j,?vi]。其中
?j?min{?i,fij}。依此进行，得到的结果是：
(a)S??，说明网络中存在增广路径?，则由标号点反向追踪找出?，转第④步；
(b)S??，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得到最小割集(S,S)。
?fij????④ 调整过程：取??min{?j}，令fij??fij??vj?????fij(vi,vj)是?上前向弧(vj,vi)是?上后向弧 其它得到新可行流{fij}，流量W(f)?W(f)??，即比原可行流流量增加了?，再转①步。
用Edmonds-Karp修正算法求解最大流问题时，也可以得到一个最小割集。最小割集的意义同Ford-Fulkerson算法得到的最小割集的意义相同。
14
山东科技大学本科毕业设计（论文）
3.3 Dinic算法
Dinic于1970年提出了Ford-Fulkerson算法的改进算法，Dinic算法的特点是将顶点按其与发点的最短距离分层。Edmonds-Karp修正算法的实质也是一种分层，如果说Ford-Fulkerson算法是采用了深度优先策略。Edmonds-Karp修正算法则是用宽度优先取代了深度优先，Dinic算法则是兼取这两种方法。在分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略（参见文献[3]）。 3.3.1 增量网络与分层增量网络
定义13：给定一个带发点vs和收点vt的容量网络D?(V,A,C)及D上的
???A(f)?{(vi,vj)|(vi,vj)?A,fij?cij}可行流{fij}后，我们定义??，因为D中任
??A(f)?{(vi,vj)|(vj,vi)?A,fji?0}何一对顶点之间至多有一条弧，所以A?(f)A?(f)??，记(vi,vj)?A(f)令
A(f)??A(f)?A(f，
并且对一切
???cij?fij,若(vi,vj)?A(f)，于是得一个带发点vs和收点vt的容量网络cij???，若(vi,vj)?A(f)??fjiD(f)?(V,A(f),C)，称之为D的关于可行流{fij}的增量网络。
为了介绍分层增量网络，我们先来介绍关于网络的一个算法——分层算法，它的基本思想是：
步骤0：把发点vs标为“已标号未检查”，vs的层数h(s)?0。
步骤1：在已标号未检查顶点中选取最早得到标号的顶点vi，转步骤2；如
果所有标号顶点都已检查，转步骤3。
步骤2：考察顶点vi的一切出弧(vi,vj)，若vj已标号，什么也不做；否则将
15
山东科技大学本科毕业设计（论文）
vj标为“已标号未检查”，并令h(j)?h(i)?1。当vi的所有出弧都考察完毕，把vi改为已检查，转步骤1。
步骤3：如果有—些顶点没有标号，则从vs到这些顶点不存在路；否则vi为
D的根，h(i)为D中最短(vs,vi)路的长。
在增量网络D(f)中应用分层算法，可以求出从发点vs到其余各顶点vi的最短路的长h(i)，h(i)就是顶点vi（关于发点vs）的层数。即vi就是D(f)的第h(i)层顶点。D(f)的第0层只有一个顶点，把顶点分层后，D(f)中
的弧又可以分为三类：
第一类为从第i层顶点到第i?1层顶点的弧； 第二类为从第i层顶点到同一层顶点的弧；
第三类为从第i层顶点到第j层顶点的弧(j?i)（参见文献[5]）。 定义14：对于带发点vs和收点vt的容量网络D?(V,A,C)，设关于可行流
,C我)们定义D(f)的子网络{fij}的增量网络D(f)?(V,A(f)，
AD(f)?(V'(f),A'(f),C)如下： V'(f)?{vt}{vi|h(i)?h(t)}A'(f)?{(vi,vj)|h(j)?h(i)?1?h(t),(vi,vj)?A(f)}{(vi,vt)|h(i)?h(t)?1,(vi,vt)?A(f)}则AD(f)称为D的关于可行流{fij}的分层增量网络。其中第0层和第h(t)层分别只有一个顶点vs和vt，AD(f)的所有弧都是由第i层顶点指向第i?1层顶点i?h(t)。
3.2 Dinic算法的基本思想及具体步骤
16
山东科技大学本科毕业设计（论文）
Dinic算法的基本思想是：从带发点vs和收点vt的容量网络D的任一可行流f0 (例如零流)开始，构造D的关于f0的分层增量网络AD(f0)，在
AD(f0)中找一条从vs到vt的增广路径?，对f0沿?进行增广得到可行流
f01，在AD(f0)中删去?上容量最小的弧，并相应修改AD(f01)上弧的容量，得到网络AD(f01)，然后可以在AD(f01)中再找一条从vs到vt的增广路径?，对f01沿?进行增广得到可行流f02，重复上述步骤依次得到D的可行流
f01,f02,,f0p?f1，因为AD(f0)只有有限条弧，每次至少删去一条弧，所以
在有限步后必然使余下的网络不再存在增广路径，vt在AD(f1)中的层数一定大于它在AD(f0)中的层数；针对AD(f1)重复上面的做法，在有限次增广后一定会得到D的可行流f2，使vt在AD(f2)中的层数更大。由于vt的层数最多为n?1（n是网络D的顶点数）。因此经过有限步后得到D的可行流fk，
D中不再有fk的增广链，这时fk就是D的最大流。Dinic算法的具体步骤
如下：
步骤0：在网络D中任意取—个可行流f0作为初始可行流，令
p?0,q?0,qfp?0f。
步骤1：(作分层增量网络)根据fqp作D的增量网络D(fqp)，再利用分层算 法构造分层增量网络AD(fqp)，如果在作分层增量网络时vt得不到标号，则 算法结束，fqp就是D的最大流；否则转步骤2。 步骤2：(寻找增广路径)
17
山东科技大学本科毕业设计（论文）
①给发点vs标号为[??,vs]，令i?s。
②如vi在AD(fqp)没有出弧，转⑤；否则在AD(fqp)中任取vi的一条出弧
(vi,vj)，转③。
③设vi的标号为[?i,?i]，其中?i为vi前面的节点，令?j?min{?i,cij}，vj获得标号 [?j,vi]。
④如果j?t，转步骤3；否则令i?j，转②。
⑤设vi的标号为[?i,?i]，如果?i?vs，在AD(fqp)中删去vi的所有入弧，所 得的网络仍记为AD(fqp)，转②；否则置q?q?1，转步骤1。
步骤3：（增广）从顶点vt的标号中的第二个元素反向追踪，求出AD(fqp)的增广路径?，在AD(fqp)中把?上的每条弧的容量cij改为cij??t，删去容量为0的弧，同时把流fqp增广为流fqp?1，把AD(fqp)中修改容量和删去弧后的网络记为AD(fqp?1)，置p?p?1，去掉网络AD(fqp)中所有顶点的标号，转步骤2。
18
山东科技大学本科毕业设计（论文）
第四章 最大流问题的应用
4.1 铁路货运列车的最优调度
4.1.1 问题叙述
某地区A、B两市之间要修建一铁路，依据地势、环境、需求等因素，修建铁路的预定方案如下：
（1）铁路的运行方式为客车与货运兼营的双轨铁路（单向单轨），在其运行的列车有旅客快车和货运列车，由于客车的运行时间是国家铁路部门早已排定的，不可更改，且规定客运优于货运，即货车在每站开出前应先明确在其到达前方车站前不会被客车赶上，否则在该站等候不能开车。又若货车的前方到达站如无停车岔道，则货车从本站开出前应明确在其前面两站的行程中不会被客车赶上否则在本站等候不能开车，余类推。 （2）铁路线内有A、B、C、D四个站，各站的岔道数为
nA?5,nB?7,nC?9及nD?11.
这些岔道可供调车用，亦可供停车卸货及洗刷车辆用。
（3）按早已排定的旅客快车时刻表，客车每天凌晨2:00从A站开出，以后每隔5小时开出一列，一昼夜共开出5列，当天最后一列的开车时间与翌晨第一列的开车时间相隔4小时。客车的行车时间在A、B站之间为3小时；在B、C站之间为2小时；在C、D站之间为5小时。
（4）在不干扰客车运行的条件下，关于货运列车的初步安排为：每天0:00从A站发出一列，以后每隔2小时发出一列，货车的行车时间在A、B站之间为5小时；
在B、C站之间为4小时；在C、D站之间为7小时。
19