无环网络最大流的一种新算法  

A New Algorithm for Solving the Maximum Flow Problem in the Network without Circle

作　　者：孙小军[1] 王志强[2] 

机构地区：[1]宝鸡文理学院数学系,陕西宝鸡721013 [2]国防科技大学信息系统与管理学院C4ISR技术国防重点实验室,湖南长沙410073

出　　处：《江西师范大学学报（自然科学版）》2009年第3期370-372,共3页Journal of Jiangxi Normal University(Natural Science Edition)

基　　金：陕西省自然科学基础研究计划(2006A12);宝鸡文理学院院级科研资助项目

摘　　要：网络最大流问题是运筹学和网络优化的重要问题之一.基于动态规划基本思想,提出了在无环网络中适用的一种网络最大流算法.该算法通过判断在各个动态阶段各节点允许通过的最大流量,最终得到终点的最大流量—网络最大流,从而大大提高了执行的效率.最后算法分析和算例表明了新算法的有效性.Maximum Flow Problem is one of the important problems in operations research and network optimization. On the basis of the idea of dynamic programming, a new algorithm is presented which is applicable in the network without circle. The efficiency of the algorithm is improved by judging the maximum flow value in each node in the dynamic stage to obtain the end-point＇ s maximum flow value. Analysis of the new algorithm and example is given to show the effectiveness of it .

关 键 词：最大流 无环网络 动态规划 算法 

分 类 号：TP224[自动化与计算机技术—检测技术与自动化装置]