《最大流算法》PPT课件

预流推进算法流程
算法过程prepare()，即首先将与s相连的边设为满流， 并将这时产生的活动结点加入队列Q。这是算法的开 始。
以后便重复以下过程直到Q为空：
(1).选出Q的一个活动顶点u。并依次判断残量网络G'中 每条边(u, v)，若h(u) = h(v) + 1，则顺着这里条边推流， 直到Q变成非活动结点（不存在多余流量）。(Push推 流过程)
(2).如果u还是活动结点。则需要对u进行重新标号： h(u) = min{h(v) + 1}，其中边(u,v)存在于G' 中。然后再 将u加入队列。(relable过程)
可以证明，通过以上算法得到的结果就是最大流。
预流推进算法示例
顶点u的通过量g(u)： 剩余图中，找入边权和与出边权和的较小值 增广时，每次找一个通过量最小的点v，从点v 向源点“推”大小为g(v)的流量 向汇点“拉”大小为g(v)的流量 尽量使剩余图中的边饱和
算法可描述为：
第1步. 令f为零流。 第2步. 若无最小费用可改进路，转第5步；否则找到最小费
用可改进路，设为P。 第3步. 根据P求delta（改进量）。 第4步. 放大f。转第2步。 第5步. 算法结束。此时的f即最小费用最大流。
inc(flow[i, j], delta) else
dec(flow[j, i], delta); until i = 1; {放大网络流} until false; end;
利用找增广路的其他流量算法
增广路的思想在于每次从源点搜索出一条前往汇点的 增广路，并改变路上的边权，直到无法再进行增广：
则称之为网络流图，记为G = (V, E, C)
可行流
可行流 对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这 一组数满足下列三条件时称为这网络的可行流，用f表示 它。

第6页/共36页
(1)为了便于弧标号法的计算，首先需要将最大流 问题（譬如图10.3.1）重新改画成为图10.3.2的形式。
图10.3.2
第7页/共36页
在图10.3.2中，每条弧 上V标ij 有两个数字，其
中，靠近点 i 的是 ，c靠ij 近点 j 的是 。如c①ji
②表示5 从0①到②的最大通过量是5（百辆），从② 到①的最大通过量是0；② ③表示从2②到2③和 从③到②都可以通过2（百辆）；等等。
例如，在图10.3.11中，从①到⑦的最短路是①— ③—⑤—⑦，代价为7，在这条最短非饱和路上取P 3 后，③—⑤变成容量为零，在下一次选择最短路时 应将③—⑤视为断路来选取最短非饱和路。另外， 选取①—③—⑤—⑦路后，③—①，⑤—③，⑦— ⑤的弧成为容量大于零的弧，可分别标上它们的代 价值为-3，-3，-1，是①—③，③—⑤，⑤—⑦的相 反数。
转入步骤④，用原图中各条弧上发点与收点数
值减去修改后的图上各点的数值，将得到正负号
相反的两个数，将这个数标在弧上，并将从正到
负的方向用箭头表示,这样就得到最大流量图。例
如原来弧(3,6) 是③ 7 0 ⑥，现在是③ 2 5 ⑥，
相减为±5，③那边为正，我们就记作③ 5⑥。
这样，就得到图10.3.9，即最大流量图。依这样的
第12页/共36页
通过第1次修改，得到图10.3.3。
图10.3.3
返回步骤①，进行第2次修改。
第13页/共36页
第2次修改： 选定①—②—⑤—⑦，在这条路中，由
于 P c25，所3 以，将 改为2c12， 改为0，c25 改
为5，c5、7 、 改为c213。c5修2 改c后75 的图变为图
10.3.4。

解决方案：可以通过建立最大流模型，求解出最优的运输路径，从而提高物流运输效率，降低运输 成本。
实际应用效果：在实际应用中，最大流问题可以有效地解决物流运输中的路径规划、车辆调度等问 题，提高物流运输效率，降低运输成本。
网络流量优化中的最大流问题
背景：随着互联网 技术的发展，网络 流量优化成为重要 问题
预流推进法的实现
预流推进法是一种求解最大流问题的算法 基本思想：通过寻找增广路径，逐步增大流值
实现步骤：初始化、寻找增广路径、更新流值、重复以上步骤直到找不到增广路径
优点：效率较高，适用于大规模网络流问题
Dinic算法的实现
初始化：设置源 点s和汇点t，初 始化网络流网络
寻找增广路径： 使用BFS寻找从 s到t的增广路径
汇报人：
EdmondsKarp算法等
扩展问题：最小 费用最大流问题 的扩展问题包括 最小费用最大流 问题、最小费用 最大流问题等。
多终端最大流问题
定义：在一个网络中，有多个源点和多个汇点，每个源点和汇点之间都有一条或多条边相连，每条边上都有一个容 量限制，求从源点到汇点的最大流量。
应用场景：多终端最大流问题在物流、交通、网络等领域有广泛的应用。
电力分配中的最大流问题
电力分配：将电力从发电站分配到各个用户 最大流问题：在电力分配中，需要找到一种最优的分配方案，使得电力分配达到最大 实际应用：在实际电力分配中，可以使用最大流算法来寻找最优的分配方案 应用效果：使用最大流算法可以大大提高电力分配的效率和准确性，降低电力损耗和成本
感谢您的观看
更新流量：沿 着增广路径更 新流量
重复步骤2和3， 直到找不到增 广路径
输出最大流值： 计算从s到t的 最大流值
Ford-Fulkerson算法的实现

S
5
I1 ∞
6 I2 ∞
7
∞ ∞
实验 E1 10
E2 2
t
I3
5
最大净收益：
（10+25）-（5+6+7） =17
2021/6/7
26
1 6 s32
43
12 25 t 39
最大净收益：(2+5+9) – ( 2+3+4 )= 16 – 最大流 9 = 7
做实验 2和3
2021/6/7
27
实验仪器和实验的输出： 构造图时要重新编号
怎样求正向割边和逆向割边？
2021/6/7
18
水流管道的最大流量由最细的管子容量决定的
2021/6/7
19
二、最大流最小割定量的应用
1、太空飞行计划问题
【问题描述：】 W 教授正在为国家航天中心计划一系列的太空飞行。每次太
空飞行可进行一系列商业性实验而获取利润。现已确定了一个 可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验 需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到 的仪器是I的子集Rj 。配置仪器Ik的费用为ck美元。实验Ej的赞 助商已同意为该实验结果支付pj美元。W教授的任务是找出一 个有效算法，确定在一次太空飞行中要进行哪些实验并因此而 配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指 进行实验所获得的全部收入与配置仪器的全部费用的差额。
1 6 s32
43
12 25 t 39
仪器：1-3中b[i]=-1的点。 实验：4-6中b[ j]=-1的点。
2021/6/7
割边：如果存在弧<i,j>， 满足：i∈S,b[i]>=0,

第九页，编辑于星期三：九点 二十九分。
第十页，编辑于：九点 二十九分。
第十二页，编辑于星期三：九点 二十九分。
第十三页，编辑于星期三：九点 二十九分。
第十四页，编辑于星期三：九点 二十九分。
第十五页，编辑于星期三：九点 二十九分。
第十六页，编辑于星期三：九点 二十九分。
第一页，编辑于星期三：九点 二十九分。
第二页，编辑于星期三：九点 二十九分。
第三页，编辑于星期三：九点 二十九分。
第四页，编辑于星期三：九点 二十九分。
第五页，编辑于星期三：九点 二十九分。
第六页，编辑于星期三：九点 二十九分。
第七页，编辑于星期三：九点 二十九分。
第八页，编辑于星期三：九点 二十九分。
第二十四页，编辑于星期三：九点 二十九分。
第二十五页，编辑于星期三：九点 二十九分。
第二十六页，编辑于星期三：九点 二十九分。
第二十七页，编辑于星期三：九点 二十九分。
第二十八页，编辑于星期三：九点 二十九分。
第十七页，编辑于星期三：九点 二十九分。
第十八页，编辑于星期三：九点 二十九分。
第十九页，编辑于星期三：九点 二十九分。
第二十页，编辑于星期三：九点 二十九分。
第二十一页，编辑于星期三：九点 二十九分。
第二十二页，编辑于星期三：九点 二十九分。
第二十三页，编辑于星期三：九点 二十九分。

3
(4,0) 4 (5,0) (1,0) (3,0) t
(2,0) 5 (2,0)
8 6 10 7 7599
6.4.3 最大流最小割定理（福特-富克森）
• 网络的最大流等于最小割集的容量
2
hw
6.4.4 求网络最大流的标号算法
• 从任一个初始可行流出发，如 0 流 • 基本算法：找一条从 s 到 t 点的增广链(augmenting path) • 若在当前可行流下找不到增广链，则已得到最大流 • 增广链中与 s 到 t 方向一致的弧称为前向弧，反之后向弧
5
hw
P165例6 (0,∞) s
(s,8) 1
9(0)
8(0)
5(0) 2(0)
7(0) 2 9(0)
(1,8) 3 5(0)
6(0)
t (3,5)
4 10(0)
1
9(5)
8(5)
3 5(5)
(0,∞) s
5(0) 2(0) 6(0)
t (4,7)
7(0)
2 (s,7)
9(0)
4 10(0) (2,7)
第二步：增广过程 1、对增广链中的前向弧，令 f=f +q(t)，q(t) 为节点 t 的标记值 2、对增广链中的后向弧，令 f=f q(t)
3、非增广链上的所有支路流量保持不变
第三步：抹除图上所有标号，回到第一步
• 以上算法是按广探法描述的，但在实际图上作业时，按深探法 进行更快捷。一次只找一条增广链，增广一次换一张图。最后 一次用广探法，以便找出最小割集
从节点 i 正向流出，可增广 q( j )=min[q( i ), cijfij] ； (3) ( j, i )是后向弧，若 fji=0，则节点 j 不标号； (4) (j, i )是后向弧，若 fji>0，则节点 j 标号为[i, q( j )]，表示

图 1 所示网络等价于图 2 所示的单源单汇网络。
x1
,2
6 ,1
1 ,1
2,2
v1
5 ,1
4,0
y1
ቤተ መጻሕፍቲ ባይዱ
3,0
1,0
1,0
3 ,1
4,4
2 ,1
s
6,0
2,2
,0
,6 t
s
,4
x2
v 4 5,3
3,2
y2
,0
6,4
v3
图2
y3
二、最大流与最小割
最大流问题是一类应用极为广泛的问题， 例如在交通运输网络中 有人流、车流、货物流，供水网络中有水流，金融系统中有现金流， 通讯系统中有信息流，等等。 定义 5 设 N (V , E, c, s, t ) 是一个网络， f 是一个流，若不存在 流 f ' ，使
定义 3
eN ( A)


f (e)
eN ( A)

设 f 是 网 络 N 的 一 个 流 ， AV ， 则 称 f (e) 为流出 A 的净流量，称 f (e) f (e)
eN ( A) eN ( A)
为流入 A 的净流量。 注 2： （1）流入、流出任何中间点的净流量为 0； （2）流出发点集 X 的净流量等于流入收点集 Y 的净流量。
'
( ,) i j A iS , jS

uij 为割 ( A, A)
N 的最小割。
注 4：割是从 A 到 A 的有向弧组成的
最大流与最小割的关系：
定理 1 设 f 是 N 的流， ( A, A) 是一个割，则： （1） Val f
eN ( A)

v5
)
vs
(1,3)
) 4 , 4 (
(0 ,1 )
vt
第三次迭代：最优解
v2
(4,4)
v4
( 5, 5)
,5 )
(2,2)
(1,4)
[vs ,1]
v1
v3
(1, 2
[ 0, ]
(2
(0,1)
v5
)
vs
(1,3)
) 4 , 4 (
(0 ,1 )
vt
四、确定网络中最大流的方法
最大流时始节点的净流出量 最大流时终节点的净流入量 最小割集的容量

割集：某连通图G上的一个边的集合。
割集容量：指割集中所有边的容量之和。 最小割集：割集中容量最小的割集。 最小割集最大流定理：网络最大流等于所有割
集中的最小割量。 标号法求得最小割集
一个简单的例子v2a1 Nhomakorabeav1
a4
a3
a2
v4
a5
Sv1 v3
v3
再看例4-2
习题

第一版：
(2,2)
[ 0, ]
(2
(0,1)
,5 )
2)
(0,4)
vs
(2,3)
4) , (3
( 5, 5)
[v5 ,1] vt
[v3 ,1]
(0 ) ,1
v1
v3 [v4 ,1]
v5
v2
(4,4)
v4
( 5, 5)
,5 )
(2,2)
(1,4)
[vs ,1]
v1
v3
(1, 2
[ 0, ]
(2
(0,1)

《网络最大流问题》PPT课件
本课件仅供大家学习学习 学习完毕请自觉删除
谢谢 本课件仅供大家学习学习
学习完毕请自觉删除 谢谢
第六章 图与网络分析
第一节 图的基本知识 第二节 树 第三节 最短路问题 第四节 网络最大流问题 第五节 最小费用最大流问题
第四节 网络最大流问题
图10-23是联结某产品产地v1和销地v6的交通网，每一
给vt标号为(v4, l(vt))，这里 l(vt)＝min[l(v4), (c4t- f4t)]=min[1, 2]=1
因vt有了标号，故转入调整过程。
(3,3) (0,+∞) vs
(5,1)
v2 (-v1,1) (4,3) v4 (v2,1) (5,3)
(1,1) (1,1) (3,0)
vt (v4,1)
(3,3)
(5,3)
(0,+∞) vs (5,1)
(1,1) (1,1)
(3,0) vt (2,1)
v1 (vs,4) (2,2) v3
(4) 检查v2。
在弧(v2，v4)上，f21=3， c24=4，f24< c24，则给
v4标号(v2, l(v4)) 。
l(v4) = min[l(v2), (c24- f24)]=min[1, 1]=1 在 弧 (v3 ， v2) 上 ， f32=1>0 ， 给 v3 标 号 ： (-v2,
便不存在路。所以，截集是从vs到的vt必经之路。
定义5 给一截集(V1, V)__，1 把截集(V1, )中V__1 所有弧的 容量之和称为这个截集的容量(简称为截量)，记为
c(V1, )，即V__1
cV1,V1
cij
(vi,vj)(V 1,V1)

(3)重复步骤(2)，直到vt成为标号点或所有标号点 都检查过。若vt成为标号点，表明得到一条vs到vt的 增广链，转入调整过程；若所有标号点都检查过， 表明这时的可行流就是最大流，算法结束。
调整过程：在增广链上，前向边流量增加l(vt)，后 向边流量减少l(vt)。
下面用实例说明具体的操作方法：例
v2 (4,3) (3,3)
vs (5,1)
(1,1) (1,1)
v1 (2,2)
v4 (5,3)
(3,0) vt (2,1)
v3
在图中给出的可行 流的基础上，求vs 到vt的最大流。
(-vv21,1)(4,3)
(3,3)
(v2,1)
v4 (5,3)
(,+∞)
vs (5,1)
(1,1) (1,1)
(v3,1)
下图中已经标示出了一个可行流，求最大流
v[2vs, 4] (4, 0)
(4, 0)
[, ∞] vs
(1, 0) (1, 0)
[v2,v44]
(3, 2)
(5, 2)
vs [v4, 3]
(2, 0)
(5, 2)
v1
[vs, 3]
(2, 2)
v5
(4, 0)
v3
[-v4, 2]
如图已经得到增广链，然后进行调整。
网络的总流量。
可行流总是存在的，例如f={0}就是一个流量为0的可 行流。
所谓最大流问题就是在容量网络中寻找流量最大的可 行流。
一个流f={fij}，当fij=cij，则称f对边(vi, vj)是饱和的， 否则称f对边(vi, vj)不饱和。对于不饱和的，其间隙为 δij=cij-fij
最大流问题实际上是一个线性规划问题。