秒懂算法 | 最大网络流的增广路算法

简介: 增广路算法是由Ford和Fulkerson于1957年提出的。该算法寻求网络中最大流的基本思想是寻找可增广路,使网络的流量得到增加,直到最大为止。即首先给出一个初始可行流,这样的可行流是存在的,例如零流。如果存在关于它的可增广路,那么调整该路上每条弧上的流量,就可以得到新的可行流。对于新的可行流,如果仍存在可增广路,则用同样的方法使流的值增大。继续这个过程,直到网络中不存在关于新的可行流的可增广路为止。此时,网络中的可行流就是所求的最大流。

1增广路算法

定理4(增广路定理)设flow是网络G的一个可行流,如果不存在从源点s到汇点t关于flow的可增广路P,则flow是G的一个最大流。

1●增广路算法思想

增广路算法是由Ford和Fulkerson于1957年提出的。该算法寻求网络中最大流的基本思想是寻找可增广路,使网络的流量得到增加,直到最大为止。即首先给出一个初始可行流,这样的可行流是存在的,例如零流。如果存在关于它的可增广路,那么调整该路上每条弧上的流量,就可以得到新的可行流。对于新的可行流,如果仍存在可增广路,则用同样的方法使流的值增大。继续这个过程,直到网络中不存在关于新的可行流的可增广路为止。此时,网络中的可行流就是所求的最大流。

该算法分以下两个过程:

(1) 找可增广路。

可采用标号法找可增广路。对网络中的每个节点j,其标号包括两部分信息(pred(j),maxl(j))。其中,pred(j)表示节点j在可能的增广路中的前一个节点;maxl(j)表示沿该可能的增广路到节点j为止可以增加的最大流量。

具体步骤如下:

第一步,源点s的标号为(0,+∞)。

第二步,从已标号而未检查的点v出发,对于边,如果flow(v,w)<cap(v,w),则w的标号为(v,maxl(w)),maxl(w)=min{maxl(v),cap(v,w)-flow(v,w)};对于边,flow(w,v)>0,则w的标号为(-v,maxl(w)),maxl(w)=min{maxl(v),flow(w,v)}。

第三步,不断重复步骤2,直到已经不存在已标号未检查的点或标到了汇点结束。如果不存在已标号未检查的点,就说明不存在关于当前可行流的可增广路,当前流就是最大流。如果标到了汇点,就找到了一条可增广路,需要沿着该可增广路进行增流,转过程(2)。

(2) 沿着可增广路进行增流。增流方法为:

先确定增流量d,即d=maxl(t),然后依据下面的公式进行增流。

image.png


增流以后的网络流依旧是可行流。

2●算法设计

采用队列LIST来存放已标号未检查的节点。根据增广路算法的思想,算法设计如下:

第一步,初始化可行流flow为零流;对节点t标号,即令maxl(t)=任意正值(如5)。

第二步,若maxl(t)>0,继续下一步;否则算法结束,此时已经得到最大流。

第三步,取消所有节点j∈V的标号,令maxl(j)=0,pred(j)=0;令LIST={s},对节点s标号,令maxl(s)=∞。

第四步,如果LIST≠∮,且maxl(t)=0,继续下一步;否则:

(1) 如果t已经有标号(即maxl(t)>0),就找到了一条增广路,沿该增广路对流flow进行增流(增流的流量为maxl(t),增广路可以根据pred回溯方便得到),转第二步。

(2) 如果t没有标号(即LIST=∮且maxl(t)=0),那么转第二步。

第五步,从LIST中移走一个节点i,寻找从节点i出发的所有可能的增广边。

(1) 对非饱和的向前边,若节点j没有标号,则对j进行标号,即令maxl(j)=min{maxl(i),cap(i,j)-flow(i,j)},pred(j)=i,并将j加入LIST中,转第四步。

(2) 对非零向后边,若节点j没有标号,则对j进行标号,即令maxl(j)=min{maxl(i), flow(i,j)},pred(j)=-i,并将j加入LIST中,转第四步。

3●增广路算法的构造实例

【例7-6】用增广路算法找出如图7-5所示的网络及可行流的最大流,其中,顶点1为源点,顶点6为汇点,边上的权为(cap,flow)。

image.png


图7-5网络及可行流

解:标号法找增广路(按顶点序号由小到大的顺序选择已标号未检查的点)如图7-6所示(注:增广路在图中用黑粗线表示)。

image.png


图7-6第一次找到的一条可增广路

沿着增广路增流,增加的流量d=3。增流后得到的新的可行流如图7-7所示。

image.png


图7-7第一次增流后的可行流

根据增广路算法,取消所有顶点的标号,给它们重新标号,如图7-8所示。

image.png


图7-8第二次找到的可增广路

沿着增广路增流,增加的流量d=2。增流后的可行流如图7-9所示。

image.png


图7-9第二次增流后的可行流

根据增广路算法,取消所有顶点的标号,给它们重新标号,如图7-10所示。

image.png

图7-10第三次找到的可增广路

沿着增广路增流,增加的流量d=1,增流后的可行流如图7-11所示。

image.png

图7-11第三次增流后的可行流


重新开始标号,标号过程进行到3号顶点后无法继续进行,当前网络中已没有关于当前可行流的可增广路,该可行流已达到了最大流,如图7-12所示。

image.png


图7-12网络最大流

目录
相关文章
|
3月前
|
机器学习/深度学习 人工智能 算法
深度学习入门:理解神经网络与反向传播算法
【9月更文挑战第20天】本文将深入浅出地介绍深度学习中的基石—神经网络,以及背后的魔法—反向传播算法。我们将通过直观的例子和简单的数学公式,带你领略这一技术的魅力。无论你是编程新手,还是有一定基础的开发者,这篇文章都将为你打开深度学习的大门,让你对神经网络的工作原理有一个清晰的认识。
|
17天前
|
机器学习/深度学习 人工智能 算法
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
垃圾识别分类系统。本系统采用Python作为主要编程语言,通过收集了5种常见的垃圾数据集('塑料', '玻璃', '纸张', '纸板', '金属'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对图像数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。然后使用Django搭建Web网页端可视化操作界面,实现用户在网页端上传一张垃圾图片识别其名称。
67 0
基于Python深度学习的【垃圾识别系统】实现~TensorFlow+人工智能+算法网络
|
1月前
|
机器学习/深度学习 人工智能 算法
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
车辆车型识别,使用Python作为主要编程语言,通过收集多种车辆车型图像数据集,然后基于TensorFlow搭建卷积网络算法模型,并对数据集进行训练,最后得到一个识别精度较高的模型文件。再基于Django搭建web网页端操作界面,实现用户上传一张车辆图片识别其类型。
74 0
【车辆车型识别】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+算法模型
|
2月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。
|
3月前
|
机器学习/深度学习 人工智能 算法
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
鸟类识别系统。本系统采用Python作为主要开发语言,通过使用加利福利亚大学开源的200种鸟类图像作为数据集。使用TensorFlow搭建ResNet50卷积神经网络算法模型,然后进行模型的迭代训练,得到一个识别精度较高的模型,然后在保存为本地的H5格式文件。在使用Django开发Web网页端操作界面,实现用户上传一张鸟类图像,识别其名称。
113 12
鸟类识别系统Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+ResNet50算法模型+图像识别
|
2月前
|
机器学习/深度学习 算法 数据挖掘
基于GWO灰狼优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
本项目展示了基于分组卷积神经网络(GroupCNN)和灰狼优化(GWO)的时间序列回归预测算法。算法运行效果良好,无水印展示。使用Matlab2022a开发,提供完整代码及详细中文注释。GroupCNN通过分组卷积减少计算成本,GWO则优化超参数,提高预测性能。项目包含操作步骤视频,方便用户快速上手。
|
2月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
本项目展示了一种基于WOA优化的GroupCNN分组卷积网络时间序列预测算法。使用Matlab2022a开发,提供无水印运行效果预览及核心代码(含中文注释)。算法通过WOA优化网络结构与超参数,结合分组卷积技术,有效提升预测精度与效率。分组卷积减少了计算成本,而WOA则模拟鲸鱼捕食行为进行优化,适用于多种连续优化问题。
|
2月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的GroupCNN分组卷积网络时间序列预测算法matlab仿真
该算法结合了遗传算法(GA)与分组卷积神经网络(GroupCNN),利用GA优化GroupCNN的网络结构和超参数,提升时间序列预测精度与效率。遗传算法通过模拟自然选择过程中的选择、交叉和变异操作寻找最优解;分组卷积则有效减少了计算成本和参数数量。本项目使用MATLAB2022A实现,并提供完整代码及视频教程。注意:展示图含水印,完整程序运行无水印。
|
2月前
|
机器学习/深度学习 算法 5G
基于BP神经网络的CoSaMP信道估计算法matlab性能仿真,对比LS,OMP,MOMP,CoSaMP
本文介绍了基于Matlab 2022a的几种信道估计算法仿真,包括LS、OMP、NOMP、CoSaMP及改进的BP神经网络CoSaMP算法。各算法针对毫米波MIMO信道进行了性能评估,通过对比不同信噪比下的均方误差(MSE),展示了各自的优势与局限性。其中,BP神经网络改进的CoSaMP算法在低信噪比条件下表现尤为突出,能够有效提高信道估计精度。
43 2
|
2月前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。