最大流问题的算法及其应用  

作　　者：李娜 

机构地区：[1]曲阜师范大学杏坛学院,山东曲阜273100

出　　处：《赤子》2013年第23期263-264,112,共3页

基　　金：黑龙江省高教综合改革试点专项项目《高职院校教学督导制度与机制建设的研究与实践》项目编号JGZ201202361.

摘　　要：本文简述了网络最大流问题，给出了最大流问题的有关概念，说明求解最大流问题的实质就是求一个最大可行流。网络最大流问题的算法是一个传统的研究课题，最早的算法是2F算法，也是当今应用最广泛的算法。本文主要介绍了最大流问题的六种算法：割集矩阵算法、图单纯形算法、表格算法、数值算法、“构造式”算法以及一种改进算法（断路法）。这六种算法都是在2F算法的基础上改进的，在解决某一类问题时比2F算法更有优势。文章最后用两个例题比较说明了这六种算法各自的利弊。

关 键 词：最大流 图单纯形算法 表格算法 数值算法 

分 类 号：O221.1[理学—运筹学与控制论]