摘要
网络最大流问题在工程和科学领域应用广泛,许多线性规划的实际问题都可转化为网络最大流的模型来求解,开辟了图论应用的新途径。为了解决现有的求解网络最大流算法存在的步骤繁复、计算量大、由于增广链选取的顺序不当而无法得到理想的最大流等问题,文中在原有算法的基础上作了一些改进,应用图的深度优先搜索原理,提出一种新的求解最大流问题的算法。该算法可以简单快速地找到增广链,提高了算法效率和可控性,易于实现,且避免了标号过程,只需要在一个图上即可完成,整个运算过程直观性强,计算方便。
The network of maximum flow is widely applied in engineering and science, a lot of the actual linear programming problem can be converted into the network of the maximum flow model to solve, opened up a new way of the application of graph theory. There are lots of steps and complicated calculation in the existing algorithm for solving the maximum networks flow, and because of improper selection order of augmented path, can not obtain the ideal maximum flow. In order to solve these problems in existing algorithm, it does some improvement of the existing algorithms, then puts forward a new algorithm for solving the maximum flow problem which makes use of depth first search theory. This algorithm can find the augmented path easily and quickly, and avoid the labeling process, the entire operation process only needs drawing a diagram to be completed,it is improving the efficiency and controllable of the algorithm and easy to realize. It is strong intuitive and convenient to calculate.
出处
《计算机技术与发展》
2012年第10期161-164,共4页
Computer Technology and Development
基金
国家自然科学基金资助项目(61070234
61071167)
关键词
最大流
增广链
增广链算法
深度优先搜索
maximum flow
augmenting path
augmenting path algorithm
depth first search
