内容发布更新时间 : 2024/12/23 8:30:42星期一 下面是文章的全部内容请认真阅读。
山东科技大学本科毕业设计（论文）
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