最大流问题及其应用
（西南林业大学理学院，中国云南昆明，650224）
更多相关毕业论文资料请到https://www.doczj.com/doc/084322166.html, 找到毕业论文相关文件夹打开，下载自己需要的论文，此篇仅供参考
摘要：网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。
本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据——Ford-Fulkerson最大流最小割定理；综述解决最大流问题的几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。
为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题——铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。
本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。
关键词：图网络流最大流
Maximum flow problem and its applications
(Southwest Forestry University,Kunming,Yunnan,650224,China)
Abstract: The network flow problem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and other areas can bring us great convenience.
The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem -- Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dinic algorithm are summarized in this paper. It also compares various algorithms to solve different problems in the pros and cons.
In order to more clearly show the application of the maximum flow problem in the production life, the paper illustrates a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight train numbers through the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, transform the actual problem into the maximum flow problem, and use the properties of graph and Ford-Fulkerson labeling algorithm, and ultimately solve the problem.
In this paper, the combination of theory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and highlights the applications.
Keywords：Graph Network flow Maximum flow
目录
第一章前言 (1)
1 前言 (1)
1.1 最大流问题的研究内容及背景 (1)
1.2 最大流问题的发展状况 (2)
1.3 选题的意义 (3)
第二章预备知识 (4)
1 图论 (4)
2 网络的基本概念 (5)
3 最大流问题核心依据——Ford-Fulkerson最大流最小割定理 (6)
第三章最大流问题的几种算法 (8)
1 标号法(Ford-Fulkerson算法) (9)
1.1 标号法(Ford-Fulkerson算法)思想 (9)
1.2 Ford-Fulkerson标号法的具体步骤 (9)
2 Edmonds-Karp修正算法 (11)
3 Dinic算法 (14)
3.1 增量网络与分层增量网络 (14)
3.2 Dinic算法的基本思想及具体步骤 (15)
第四章最大流问题的应用 (17)
1 铁路货运列车的最优调度 (17)
1.1 问题叙述 (17)
1.2 问题分析 (17)
1.3 问题求解 (20)
1.4 问题总结 (25)
第五章结论 (26)
参考文献 (27)
指导老师简介 (28)
致谢 (29)
第一章前言
1 前言
1.1 最大流问题的研究内容及背景
最大流问题是一类网络分析问题，它是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题。比如交通运输网络中的人流、车流、物流、供水网络中的水流、金融系统中的现金流、通信系统中的信息流等等，都属于最大流问题（参见文献[1]）。
在对最大流问题进行研究的过程中，人们建立了最大流问题较为完善的理论，同时开发了大量的算法，如Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic 算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。近年来，随着计算机科学技术和网络的快速发展，网络最大流问题得到了更深入的研究，并极大地推动了最大流问题的研究进展（参见文献[2-5]）。
以图论理论基础来研究最大流问题是运筹学中的一种重要方法。
在自然界和人类社会的实际生活中，用图形来描述某些对象(或事物)之间具有某种特定关系常常感到特别方便，例如用工艺流程图来描述某项工程中各工序之间的先后关系；用网络图来描述某通讯系统各小通讯站之间信息传递关系；用交通图来描述某地区内各城市之间的铁路连接关系等等（参见文献[6-7]）。
图论是组合数学的—个分支，与其他的数学分支如群论、矩阵论、概率论、拓扑学、数值分析有着密切的联系，其应用十分广泛，是近年来较为活跃的数学分支之一（参见文献[8]）。它的产生和发展历经了二百多年的历史，瑞士数学家欧拉(L．Euler)在1736年解决了当时颇为有名的一个数学难题，即哥尼斯城堡七桥问题，从而使他成了图论和拓扑学的创始人（参见文献[9-10]）。早期的图论与数学游戏有密切的联系，如哈密尔顿的周游世界问题、迷宫问题、博奕问题以及棋盘上马的行走路线之类的难题等吸引了许多学者。20世纪后，图论的应用渗透到许多其他学科领域，如物理、化学、信息学、运筹学、博奕论、计算机网络、社会学以及集合论、矩阵论等。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论
成为数学领域中发展最快的分支之一，也成为现代研究最大流问题的一个重要工具。
1.2 最大流问题的发展状况
最大流问题是早期的线性网络最优化的一个例子。最早研究这类问题的是美国学者希奇柯克（Hitchcock），1941年他在研究生产组织和铁路运输方面的线性规划问题时提出运输问题的基本模型；后来柯普曼（Koopmans）在1947年独立地提出运输问题并详细地对此问题加以讨论；从上世纪40年代早期开始，康脱洛维奇（Kantorovich）围绕着运输问题作了大量的研究，因此运输问题又称为希奇柯克问题或康脱洛维奇问题。与一般线性规划问题不同，它的约束方程组的系数矩阵具有特殊的结构，这就需要采用不同的甚至更为简便的求解方法来解决这种在实际工作中经常遇到的问题。运输问题不仅代表了物资合理调运、车辆合理调度等问题，有些其他类型的问题经过适当变换后也可以归结为运输问题。后来把这种解决线性网络最优化的方法与最大流问题相结合，同时推动了最大流问题的研究与进展。
国外学者从算法角度考虑，对于最大流问题的求解提出了很多可行的解法，如表上作业法、图上求解法以及应用计算机实现的启发式多种算法等，其基本上可以总结如下：
表上作业法是解决一般最大流问题最常用的解法，因其求解工作均在运输表上进行而得名。它是一种迭代算法，迭代步骤为：先按某种规则找出一个初始解；再对现行解作最优性判别；若该解不是最优解，就在表上对它进行调整改进，从而得出一个新解，再重复判别改进的过程，直至得到最大流问题的最优解为止。
最短路线法。当已知某物资从出发地运往目的地，可有多条运输路线供选择，这时可构造费用网络图，用求最短路线的方法，选择最优的运输方案，需画出各种运输路线的线路图及图上每一条边（或弧）上的距离或费用（也可以用邻接矩阵表示），然后用Dijkstra标号法或邻接矩阵法求最优运输路线。
国内学者对于最大流问题的研究主要可以分为三个角度：一是在国外算法的基础上，对最大流问题算法的改进研究；二是从目标函数的角度，在最大流问题中有时要同时考虑成本最小、运输过程中货物损坏率最低以及单位运价变化的调整等多个目标；从约束函数的角度，有研究供给量和需求量在某个区间变化的不确定型运输问题、有时间窗口的运输问题等。
1.3 选题的意义
在日常生活和生产中我们时常遇到一些网络图。如交通图、旅游线路图、管道系统图等。在优化理论中所谓图就是上述各类图的抽象和概括，用图来描述我们的研究对象，以及这些对象之间的相互联系。例如旅游管理、网络通信、交通运输、金融系统等问题都可以用网络图来描述。
最大流问题就是就是在一个有向连通图中，指定一点为发点，另一点为收点，其余的点为中间点，在所有的点都能承载的情况下能通过此网络图的最大可行流，即发点发往收点的最大可行流。本课题的意义在于掌握最大流问题的基本理论和算法来解决实际应用问题，提高生产的有效性和生产设备的有效利用率。
最大流问题应用极为广泛，很多生活中的问题都可转化为最大流问题，其难点是从实际中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。
第二章 预备知识
1 图论
所谓“图论”，顾名思义是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映一些对象之间的关系。图形中的点表示对象(如工序、选手、通讯站等)，两点之间的有向或无向连线表示对象之间具有某种特定的关系(如先后关系、胜负关系、传递关系、连接关系等)（参见文献[13-14]）。
物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连接起来的图进行模拟。这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的
i v v ,相对位置如何，都是无关紧要的（参见文献[15-16]）
。 定义1：两点之间不带箭头的连线称为边，一条连接j i v v ,的边记为s v (或],[j i v v )，表示边的集合。
定义2：两点之间带箭头的连线称为},,{21m e e e E ?=弧，一条以i v 为始点j v 为终点的弧记为},,{),,(21m j i i a a a A v v a ?==表示弧的集合。
定义3：由点和边构成的图为无向图，记为),(E V G =；由点和弧构成的图为有向图，记为),(A V D =.
定义4：在无向图G 中，若存在一个点边交错序列),,,,,,(112211k k k i i i i i i i v e v e v e v --?，满足 )1,2,1](,[1-?==+k t v v e t t t i i i ，则称之为一条联结1i v 和k i v 的链，记为),,,(21k i i i v v v ?,若k i i v v =1，则称之为圈。
定义5：在有向图D 中，若存在一个点弧交错序列),,,,,(112211--?k k i i i i i i a v a v a v ，弧t i a 的始点为t i v ，终点为1+t i v ，记为),(1+=t t t i i i v v a ，则称这条点弧的交错序列为从1i v 到k i v 的一条路，记为),,,(21k i i i v v v ?。若路的第一点和最后一点相同，则称之为回路。链与路
中的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。 定义6：如果对于一个无向图G 的每一条边，相应有一个权数ij w ，则称这样的图为赋权图，记为),,(C E V G =。
定义7：如果对于一个有向图D 的每一条弧，相应有一个权数ij c ，称这样的图为网络,记为),,(C A V D =。
一般在网络图中，每条弧的权，不是表示弧的长度、而是表示弧的宽度，即代表距离、费用、通过能力(容量)等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络（参见文献[17]）。
定义8：在图G 中，若任何两个点之间至少有一条链（或一条路），则称G 是连通图，否则，称为不连通图。
2 网络的基本概念
假设要把起点的一批流转物运送到终点去，在每一弧上通过流转物的总量不能超过这条弧上的容量，问题是应该怎样安排运送，才能使从起点运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究内容（参见文献[15]），以下讨论的网络均为只有一个发点s v 和一个收点t v 的容量网络(,,)D V A C =。
定义9：对任意容量网络(,,)D V A C =中的弧(,)i j v v 有流量ij f ，称集合{}ij f f =为网络D 上的一个流，称满足下列条件的流f 为可行流：
(1)容量限制条件：对D 中每条弧(,)i j v v ，有ij ij c f ≤≤0；
(2)平衡条件：
①对中间点i v ，有i j k i j k
f f =∑∑(即中间点i v 的物资的输入量与输出量相等)。
②对收、发点,t s v v 有si jt i j
f f W ==∑∑(即从s v 点发出的物资总量等于t v 点入
的量) ，W 为网络流的总流量。
在容量网络(,,)D V A C =中ij c 表示弧(,)i j v v 的容量，令ij x 为通过弧(,)i j v v 的流量，显然有0ij ij x c ≤≤，流{}ij x 应遵守点守恒规则，即：
,ij ji W i s x x i s t W i t
+=??-=≠??-=?
∑∑ 称为守恒方程。 定义10：对任意容量网络(,,)D V A C =，寻求一可行流f 使得流量W 取得极大值，这个可行流f 便称为最大流。
定义11：在容量网络(,,)D V A C =中，若μ为网络中从发点s v 到收点t v 的一条路，给
μ定向为从s v 到t v ，μ上的弧凡与μ同向称为前向弧。凡与μ反向称为后向弧，其集
合分别用μ+和μ-表示，f 是一个可行流，如果满足
0(,)0(,)ij ij i j ij ij i j f c v v c f v v μμ
+-?≤<∈??≥>∈?? 则称μ为从s v 到t v 的(关于f 的)增广链。
定义12：在容量网络(,,)D V A C =中，若有弧集'A 为A 的子集，将D 分为两个子图12,D D ，其顶点集合分别记,S S ，,S S V S S ==? ，,s t v v 分别属于,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 。
3 最大流问题核心依据——Ford-Fulkerson 最大流最小割定理 Ford-Fulkerson 最大流最小割定理是由Ford 和Fulkerson 在1956年提出的，
是图论的核心定理。
定理1：（Ford-Fulkerson 最大流最小割定理）任一容量网络D 中，从s v 到t v 的最大
流{}ij f 的流量等于分离,s t v v 的最小割的容量。
证明：设在D 中从s v 到t v 的任一可行流{}ij x 的流量为W ，最小割集为(,)S S ，最小割集的容量为(,)C S S 。这个定理的证明分两步：
? 我们先证明(,)W C S S ≤：
由守恒方程可得：
()
()()()
(3.1)
ij ji i S j j
ij ji ij ji i S j S i S j S
ij ji i S j S W x x x x x x x x ∈∈∈∈∈∈∈=-=-+-=-∑∑∑∑∑∑∑∑∑ 因此有：()(,)ij ji ij ij i S j S i S j S i S j S
W x x x c C S S ∈∈∈∈∈∈=-≤≤=∑∑∑∑∑∑。
? 下面我们证明一个可行流是最大流，当且仅当不存在关于它的从
s v 到t v 的增广路
径： 必然性：显然，因为如果存在增广路径，还可以继续增广，流就不是最大流。 充分性：假设可行流{}ij x 是一个不存在关于它的增广路径的流，对于最小割集(,)S S ，有对任意,i j S ∈，存在从i v 到j v 的增广路径，而对任意,i S j S ∈∈，不存在从i v 到j v 的增广路径，由定义可知对任意,i S j S ∈∈有：
,0ij ij ji x c x ==
由公式(3.1)可知：(,)ij i S j S
W c C S S ∈∈==∑∑。
即流的值等于割集的容量，定理得证。
第三章 最大流问题的几种算法
最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大流问题。下面用数学语言来说明最大流问题：
一、设有一个有向连通图G(V,A)，在V 中指定一点称为发点s,和另外一点为收点t ，其余的称为中间点，弧（arc ）集A 中每条弧（i ，j ）上有非负数ij c 称为这弧的容量，记容量集为c={ij c }，称这样的图为一个网络，记为G(V,A, c )（注：当（i ，j ）不是弧时ij c =0）。
二、在弧集A 上的弧（i ，j ）定义一非负数ij f ，称为弧（i ，j ）上的流量，流量的集合f={ij f }称为网络的一个流，满足下列条件的称为可行流：
1）容量限制条件，所有的弧的流量ij f 不大于弧的容量ij c ；
2）平衡条件，对所有的中间点，流入的流量和等于流出的流量和，发点流出的流量F 等于流进收点的总流量F.
最大流问题就是求总流量最大达可行流。
求解最大流问题存在许多算法，这一节将介绍几种常用算法。
1 标号法(Ford-Fulkerson 算法)
1.1标号法(Ford-Fulkerson 算法)思想
Ford-Fulkerson 标号法是一种找最大流f 的算法。它是由Ford 和Fulkerson 于1957年最早提出的，其基本思想是从任意一个可行流出发寻找—条增广路径，并在这条增广路径上增加流量，于是便得到一个新的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量……，继续这个过程，一直到找不到新的增广路径为止（参见文献[2]）。
采用Ford-Fulkerson 标号法求解最大流问题时，在标号过程中，一个点仅有下列三种状态之一：标号已检查(有标号且所有相邻点都标号了)；标号未检查(有标号，但某些相邻点未标号)；未标号（参见文献[6]）。
Ford-Fulkerson 标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献[18]）。现在我们考虑只有一个发点s v 和一个收点t v 的容量网络，应用Ford-Fulkerson 标号算法求解它的最大流，
1.2 Ford-Fulkerson 标号法的具体步骤
A:标号过程
步骤0 确定一初始可行流{}ij f ，可以是零流。
步骤1 给发点s v 以标号[,]s v ∞。
步骤2 选择一个已标号但未检查的点i v ，并作如下检查：
① 对每一弧(,)i j v v ，若j v 未给标号，而且ij ij c f >时，即流出未饱和弧,给j
v 以标号[,]j i v θ；
② 对每一弧(,)j i v v ，若j v 未给标号，而且0ji f >时，即流入非零流弧，给j
v 以标号[,]j i v θ-；
其中：(,)min{,},(,)ij ij i j j i ji j i c f v v f v v θθαα?-?==???若为流出未饱和弧若为流入非零流弧
步骤3 重复步骤2直到收点t v 被标号，或不再有顶点可以标号为止。如果t v 点给了
标号说明存在一条增广路径，故转向增广过程B 。如若t v 点不能获得标号，
而且不存在其它可标号的顶点时，算法结束，所得到的流便是最大流。
B ：增广过程
由终点t v 开始，使用标号的第二个元素构造一条增广路径μ(点t v 的标号的第二个
元素表示在路中倒数第二个点的下标，而这第二个点的标号的第二个元素表示倒数第三个点的下标等等)，在μ上作调整得新的可行流{}ij f ，(标号的第二个元素的正负号表示通过增加或减少弧流来增大流值)。令θ为t v 标号的第一个元素的值，作
(,)(,)ij i j ij ij j i ij f v v f f v v f θμθμ?+??=-????是上前向弧是上后向弧
其它 以新的可行流{}ij f 代替原来的可行流，去掉所有标号，转标号过程的步骤1。
采用Ford-Fulkerson 标号算法求解最大流问题，同时得到一个最小割集。最小割集的意义是：网络从发点到收点的各个通路中，由容量决定其通过能力，通常我们将最小割集形象地称为这些通路的咽喉部分，或叫做“瓶颈”，它决定了整个网络的通过能力，即最小割集的容量的大小影响总的流量的提高。因此，为提高总的流量，必须首先考虑改善最小割集中各小弧的流量，提高它们的通过能力（参见文献[14]）。
1 m m m m m m m m f e d c a b t
s 图3.2.1
2 Edmonds-Karp 修正算法
Ford-Fulkerson 标号算法理论上存在着严重的弱点，以下图3.2.1为例各边上的权是它们的容量，其最大流流量为2m ，若增广路径选择得不好,即交替地采用sabeft 和sdebct 作为增广路径，则每次增广只能使总的流量增加1,当初始流选为零流，无疑需作21m 次的增加流量才能使之达到最大，可见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 v 和一个收点t v 的网络图，Edmonds-Karp 修正算法
的主要步骤是：
① 确定一初始可行流{}ij f ，其流量)(f W 。
② 检验当前所确定可行流是否是网络中的最大流，若不是，需进一步调整(检验一个
可行流是否为最大流。只要检查一下当前可行流是否还存在增广路径，若存在，则说明当前可行流还不是最大流，否则是最大流)。
③ 将当前的可行流调整成一个流量更大的新可行流，再由②检验。
同样地，我们通常用观察法确定网络的—个初始可行流。对于较为复杂的网络，至少能把初始可行流取为零流。通过在网络上标号的方法能系统地寻找出当前可行流的增广路径，它的基本思想是：从起点s v 起，逐步寻找s v 至各点i v 间的增广路径，若
能找到s v 至i v 的一条增广路径，则给点i v 标号[,]
i i θα（其中第一个标号i θ即为s v 至i v 这条增广路径上的最大可调整量，第二个标号i α则表示这条可行流上点i v 的前一点是i α点）。根据标号可反向追踪而写出这条增广路径。在逐步扩大已标号的过程中，一旦终点t v 标上号，表示已找到一条由s v 至t v 的增广路径。反之，如果标号过程进行至某一步中止了，而t v 尚未标号，则表明对当前的可行流，网络中不存在任何增广路径。当前可行流即为最大流。Edmonds-Karp 修正算法的具体步骤如下：
① 给发点s v 标号[,]s v ∞，含义为s v 至s v 的增广路径已找到，前一点为s v ，这条增广
路径上的调整量为∞。选与s v 关联的从s v 流出的未饱和弧(,)s i v v 或流入s v 的非零流弧(,)i s v v ，给i v 标号[,]i s v θ (对于流出弧)或[,]i s v θ- (对于流入弧)。
其中：(,)(,)si si s i i si
i s c f v v f v v θ?-?=???若为流出未饱和弧若为流入非零弧 ② 将顶点集分为互补的二个点集S 、S ，其中S 为已标号点集，S 为未标号点集； ③ 考虑所有这样的弧(,)i j v v 或(,)j i v v ，其中,i j v S v S ∈∈。若弧(,)i j v v 为从i v 流出的
未饱和弧，则给j v 标号[,]j i v θ。其中min{,}j i ij ij c f θθ=-；若弧(,)j i v v 为流入i v 的非零流弧，则给j v 标号[,]j i v θ-。其中min{,}j i ij f θθ=。依此进行，得到的结果是：
(a)S =?，说明网络中存在增广路径μ，则由标号点反向追踪找出μ，转第④步； (b)S ≠?，标号已进行不下去，说明对于当前可行流。网络中已无新的增广路径，当前可行流即为最大流，同时得到最小割集(,)S S 。
④ 调整过程：取min{}j j v μθθ∈=，令(,)(,)ij i j ij ij j i ij f v v f f v v f θμθμ?+??=-????是上前向弧是上后向弧其它
得到新可行流{}ij f ，流量()()W f W f θ=+，即比原可行流流量增加了θ，再转①步。
用Edmonds-Karp 修正算法求解最大流问题时，也可以得到一个最小割集。最小割集的意义同Ford-Fulkerson 算法得到的最小割集的意义相同。
3 Dinic 算法
Dinic 于1970年提出了Ford-Fulkerson 算法的改进算法，Dinic 算法的特点是将顶点按其与发点的最短距离分层。Edmonds-Karp 修正算法的实质也是一种分层，如果说Ford-Fulkerson 算法是采用了深度优先策略。Edmonds-Karp 修正算法则是用宽度优先取代了深度优先，Dinic 算法则是兼取这两种方法。在分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略（参见文献[3]）。
3.1 增量网络与分层增量网络
定义13：给定一个带发点s v 和收点t v 的容量网络(,,)D V A C =及D 上的可行流{}
ij f 后，我们定义(){(,)|(,),}(){(,)|(,),0}
i j i j ij ij i j j i ji A f v v v v A f c A f v v v v A f +-?=∈??，因为D 中任何一对顶点之间至多有一条弧，所以()()A f A f +-=? ，记()()()Af A f A f +-= ，并且对一切(,)()
i j v v A f ∈令,(,)()(,)()ij ij i j ij ji
i j c f v v A f c f v v A f +-?-∈?=?∈??若，若，于是得一个带发点s v 和收点t v 的容量网络()(,(),)D f V A f C =，称之为D 的关于可行流{}ij f 的增量网络。
为了介绍分层增量网络，我们先来介绍关于网络的一个算法——分层算法，它的基本思想是：
步骤0：把发点s v 标为“已标号未检查”，s v 的层数()0h s =。
步骤1：在已标号未检查顶点中选取最早得到标号的顶点i v ，转步骤2；如果所有标
号顶点都已检查，转步骤3。
步骤2：考察顶点i v 的一切出弧(,)i j v v ，若j v 已标号，什么也不做；否则将j v 标为“已
标号未检查”，并令()()1h j h i =+。当i v 的所有出弧都考察完毕，把i v 改为已检查，转步骤1。
步骤3：如果有—些顶点没有标号，则从s v 到这些顶点不存在路；否则i v 为D 的根，
()h i 为D 中最短(,)s i v v 路的长。
在增量网络()D f 中应用分层算法，可以求出从发点s v 到其余各顶点i v 的最短路
的长()h i ，()h i 就是顶点i
v （关于发点s v ）的层数。即i v 就是()D f 的第()h i 层顶点。()D f 的第0层只有一个顶点，把顶点分层后，()D f 中的弧又可以分为三类：
第一类为从第i 层顶点到第1i +层顶点的弧；
第二类为从第i 层顶点到同一层顶点的弧；
第三类为从第i 层顶点到第j 层顶点的弧()j i <（参见文献[5]）。
定义14：对于带发点s v 和收点t v 的容量网络(,,)D V A C =，设关于可行流{}ij f 的增量网络()(,(),)D f V A f C =，我们定义()D f 的子网络''()((),(),)AD f V f A f C =如下： ''(){}{|()()}
(){(,)|()()1(),(,)()}{(,)|()()1,(,)()}t i i j i j i t i t V f v v h i h t A f v v h j h i h t v v A f v v h i h t v v A f =<==+<∈=-∈ 则()AD f 称为D 的关于可行流{}ij f 的分层增量网络。其中第0层和第()h t 层分别只有一个顶点s v 和t v ，()AD f 的所有弧都是由第i 层顶点指向第1i +层顶点()i h t <。
3.2 Dinic 算法的基本思想及具体步骤
Dinic 算法的基本思想是：从带发点s v 和收点t v 的容量网络D 的任一可行流0f (例如零流)开始，构造D 的关于0f 的分层增量网络0()AD f ，在0()AD f 中找一条从s v 到t v 的增广路径μ，对0f 沿μ进行增广得到可行流10f ，在0()AD f 中删去μ上容量最小的弧，并相应修改10()AD f 上弧的容量，得到网络10()AD f ，然后可以在10()AD f 中再找一条从s v 到t v 的增广路径μ，对10f 沿μ进行增广得到可行流20f ，重复上述步骤
依次得到D 的可行流120001,,,p f f f f = ，因为0()AD f 只有有限条弧，每次至少删去一条弧，所以在有限步后必然使余下的网络不再存在增广路径，t v 在1()AD f 中的层数一定大于它在0()AD f 中的层数；针对1()AD f 重复上面的做法，在有限次增广后一定会得到D 的可行流2f ，使t v 在2()AD f 中的层数更大。由于t v 的层数最多为1n -（n 是
网络D 的顶点数）。因此经过有限步后得到D 的可行流k f ，D 中不再有k f 的增广链，
这时k f 就是D 的最大流。Dinic 算法的具体步骤如下：
步骤0：在网络D 中任意取—个可行流0f 作为初始可行流，令00,0,p q p q f f ===。 步骤1：(作分层增量网络)根据p q f 作D 的增量网络()p q D f ，再利用分层算法构造分
层增量网络()p q AD f ，如果在作分层增量网络时t v 得不到标号，则算法结束，p q f 就是D 的最大流；否则转步骤2。
步骤2：(寻找增广路径)
①给发点s v 标号为[,]s v +∞，令i s =。
②如i v 在()p q AD f 没有出弧，转⑤；否则在()p q AD f 中任取i v 的一条出弧(,)i j v v ，转③。 ③设i v 的标号为[,]i i θα，其中i α为i v 前面的节点，令min{,}j i ij c θθ=，j v 获得标号
[,]j i v θ。
④如果j t =，转步骤3；否则令i j =，转②。
⑤设i v 的标号为[,]i i θα，如果i s v α≠，在()p q AD f 中删去i v 的所有入弧，所得的网络仍记为()p q AD f ，转②；否则置1q q =+，转步骤1。
步骤3：（增广）从顶点t v 的标号中的第二个元素反向追踪，求出()p q AD f 的增广路径
μ，在()p q AD f 中把μ上的每条弧的容量ij c 改为ij t c θ-，删去容量为0的弧，
同时把流p q f 增广为流1p q f +，把()p q AD f 中修改容量和删去弧后的网络记为1()p q AD f +，置1p p =+，去掉网络()p q AD f 中所有顶点的标号，转步骤2。