点和边有容量约束的网络最小费用最大流算法

• 作者: 厍向阳
• 来源期刊: 计算机应用研究
• 关键词: 网络最小费用最大流 邻接矩阵 容量约束 残量网络
• 年，卷（期）: 2010,（8）
• 页码范围: 3112-3114,3119
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2010.08.081

摘要

分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法.概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念.依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法.该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流.最后,通过实例进行了算法测试和比较.算法测试表明:点和边有容量约束的网络最小费用最大流算法是完全可行和有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	厍向阳	西安科技大学计算机科学与技术学院	38	277	10.0	14.0