求解网络最大流问题的标号算法

给出了一种新的求解网络流问题的标号算法,对每个顶点进行标号,顶点有几个人弧,即有几个标号,每次在选择路径时先选取只有一个标号的路径,当所有单标号的路径走完时,再按照弧容量较大且最短的路径选择增广链.通过对Ford-Fulkerson标号算法进行改进,使得该算法容易理解,且又避免了Ford-Fulkerson标号算法在求解网络最大流问题时需经过多次的调整与标号,从而大大提高了求解最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性.     

基于深度优先的一种网络最大流求解法

网络最大流问题在工程和科学领域应用广泛,许多线性规划的实际问题都可转化为网络最大流的模型来求解,开辟了图论应用的新途径.为了解决现有的求解网络最大流算法存在的步骤繁复、计算量大、由于增广链选取的顺序不当而无法得到理想的最大流等问题,文中在原有算法的基础上作了一些改进,应用图的深度优先搜索原理,提出一种新的求解最大流问题的算法.该算法可以简单快速地找到增广链,提高了算法效率和可控性,易于实现,且避免了标号过程,只需要在一个图上即可完成,整个运算过程直观性强,计算方便.     

基于一个网络图最大流算法的改进

现有的求解网络最大流算法,存在由于增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题.针对上述问题展开讨论,并对一些最大流算法进行改进.利用分层网络及容差的概念,在选择增广链的时候优先选择路径最短且容差较大的路径,并将已饱和的弧画上终止符.最后通过具体的算例验证了改进算法可以简单快速地找到增广链,且避免了标号过程,只需要在一个图上即可完成.整个运算过程,直观性强,计算方便.改进的算法较其他的算法具有高效性和实用性的优势.     

基于增广链修复的最大流求解算法

NW小世界网络及BA无标度网络是现实中常见的两种网络,这两种网络中任意两点之间有极大可能存在多条路径,若舍弃饱和增广链并重新寻找增广链,则效率不高,因此针对网络的这一特性提出了一种增广链修复的最大流求解算法.该算法沿最短增广链调整流量后,保留路径上残余的非饱和弧,并用贪心法则选择合适的中继节点修复断开的增广链,提高增广链使用效率.通过对NW小世界网络和BA无标度网络建模仿真,得到并验证了所提算法在这两种网络上的运行速度数倍于Ford-Fulkerson算法且其空间复杂度仅有Dinic算法的一半,因此所提算法能够高效处理更大规模网络流问题,以适应日益膨胀的通信网络和交通运输网络.     

一种求解网络图最大流的新算法

给出一种求解网络最大流的新算法,该算法是针对增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念,在选择增广链时优先选择路径最短且度差较大的路径,相同层次度差相同时优先选择容差较大的路径,在饱和的弧上画上终止符。最后用实例进行了验证并和Ford—Fulkerson算法做了比较,体现了它的高效性,避免了标号,且只需要在一个图上即可完成。整个运算过程直观性强,计算方便。     

求解最小费用最大流的新方法

文中给出了一种求解网络最小费用最大流的新方法,寻找由始点到终点的每条有向链,找到有向链可通过的最大容量,根据最大容量计算出此条有向链的最小费用最大流,根据最大容量和最小费用最大流可以计算出单位费用.选取单位费用最小的有向链进行最大容量的增广.文中通过对最小费用路算法进行改进,使得该算法容易理解,却又避免了最小费用路算法每次都要经过剩余网络进行增广,从而大大提高了求解最小费用最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性     

基于预流推进的最小标号最大流算法

针对原始最高标号预流推进算法中的回溯现象导致其在部分网络中执行效率低下的问题,提出了基于预流推进的最小标号算法。该算法仍以预流推进为基础,但在选取活跃节点时依据贪心原则寻找最小标号活跃节点作为调整点,同时还需构造回溯检验方法终止回溯现象以提升算法效率。在仿真实验中,该算法能够适应各类复杂网络,并在稀疏网络中具有最高标号预流推进算法5倍以上执行速度;在被应用于图像分割领域时,该算法也具有50%以上性能提升。提出的基于预流推进的最小标号最大流算法能够满足大规模网络流量分配、计算机视觉图像处理等需求。     

网络最大流问题求解的符号ADD增广路径算法

本文通过对网络及网络最大流问题的符号代数判定图（ADD）描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法.与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善.实验结果表明,本文算法是切实有效的,且可处理更大规模的问题.     

收缩邻居节点集方法求解有向网络的最大流问题

最大流问题在许多领域有广泛的应用,然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题.对一个给定的有向网络,文中提出一种收缩邻居节点集的方法(CNA)求解其最大流.该方法通过收缩邻居节点集有效降低网络规模,使经典算法及改进算法可直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明CNA不仅平均能将目标网络的规模降至初始网络的一半,且能以较小的误差求得初始网络的最大流.     

基于最大流的车辆容迟网络路由算法

为提高车辆容迟网络的吞吐率,将一对节点之间的数据传输过程视为最大流问题,提出基于最大流的车辆容迟网络路由算法。容迟网络中的最大流问题被转化为静态网络中的问题,从而可用最大流方案进行求解。实验结果证明,该算法的预测准确率高于传统算法,附带的额外开销较小。