网络最大流的最大容量有向路算法  

The Maximal Capacity of Directed Path Algorithm on Maximum Flow Network

作　　者：郑桂君[1] 张薇[2] 

机构地区：[1]湛江师范学院,广东湛江524300 [2]东北大学,辽宁沈阳110004

出　　处：《廊坊师范学院学报（自然科学版）》2009年第6期22-24,共3页Journal of Langfang Normal University(Natural Science Edition)

摘　　要：针对单源、单汇网络给出最大流问题的一个新算法——最大容量有向路算法,算法的核心思想是利用分层原理在增量网络中反复寻找从源点到汇点的在一定规则下的容量最大的有向路,直至找不到有向路为止。给出算法的复杂度为O(mn)与最大流问题的两个具有代表性的算法——Ford-Fulkerson算法和Dinic算法,作了复杂性和实例比较,结论是最大容量有向路算法的效果好于Ford-Fulkerson,算法不低于Dinic算法。该算法完全能够编程实现,仿真试验结果表明,算法效果良好。A new algorithm-the maximal capacity of directed path algorithm aiming at single source and single sink net- work about maximum flow problem is given. The core idea of the maximal capacity of directed path algorithm is to find the maximal capacity of directed path with special regulation in incremental network using delamination principle from source to sink up to nothing. The complexity of this new algorithm also has been studied that is O（ mn）. The comparision on complexity and examples with being provided with two representative algorithms - Fordfulkerson algorithm and Dinic algorithm has been done. The effect of the new algorithm is better than the effect of Fordfulkerson algorithm and not low- er than the effect of Dinic algorithm. The algorithm could be achieved by programming entirely. Emluator experiment in- dicates the effect of the new algorithm better.

关 键 词：分层 增量网络 最大容量有向路算法 有向路 复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]