摘 要:本文主要研究网络流中的最小费用及最大流算法。最短路问题作为最小费用流的派生问题，在理论与实际中都有着重要的应用。因此，我们首先是对原始-对偶理论、最短路问题及其网络流的一些问题和算法进行探讨，以便进一步理解并优化最小费用流的问题。最小费用流是本文的主要研究对象，我们阐述了最小费用流问题已有的主要理论和几个流行算法，对这些算法分别进行了简单的评述，并给出具体的实例来说明问题。最后，我们在标号法的基础上做了些修改，给出了一种修改后的算法，并结合一个具体事例解释了修改后的算法思想。鉴于此，我们还对标号法做了重点的阐述。
关键词：最小费用流；增广链；最短路问题；标号法
目录
摘要
ABSTRACT
第1章 绪论-1
1.1 最小费用流研究背景及意义-1
1.2 最小费用流研究的发展状况-1
1.3 主要创新及各章的简介-2
第2章 基本原理-3
2.1 基本概念-3
2.2 最小费用流的数学描述-5
2.3 主要理论-6
2.4最短路问题-7
第3章 最小费用流问题的流行算法描述及分析-9
3.1 最优性条件-9
3.2 消圈算法-9
3.3 最小费用增广路算法-10
3.4 原始-对偶算法-10
3.5 标号法-10
3.5.1 算法的基本定理-10
3.5.2 算法的具体步骤-11
3.5.3 算法的实例-11
3.5.4 算法的评述-12
第4章 修改后的一种算法-13
4.1算法步骤-13
4.2 算法思想-13
4.3算法实例-13
4.4算法总结-15
第5章 总结与展望-17
5.1结论-17
5.2不足之处及未来展望-17
参考文献-19
致谢-21
