大规模网络最大流对偶图算法模型及实现  

A Dual Graph Algorithm Model and Its Implementation of the Maximun Flow on the Large-scale Networks

作　　者：靳小红[1,2] 冯云芝[1] 薛占熬[1] 

机构地区：[1]河南师范大学计算机与信息技术学院,河南新乡453007 [2]新乡广播电视大学,河南新乡453003

出　　处：《河北师范大学学报（自然科学版）》2010年第1期31-35,共5页Journal of Hebei Normal University：Natural Science

基　　金：河南省重点科技攻关项目(092102210149)

摘　　要：在网络最大流算法的研究中,为了减少计算量,提出了许多改进的方法.基于图论中的最大流最小割定理,利用网络流图的对偶图的最短路径求网络最大流,对求最短路径的Dijkstra算法进行了研究,给出了一种改进的Dijkstra算法模型,该算法采用了堆排序中的小根堆来选择最短路径结点,使用集合运算对堆中的结点进行处理,使得参加运算的结点数减少,提高了算法的效率.In the study of the maximum flow algorithm,improved methods are proposed for reducing the calculation volume.Based on the theorem of max-flow min-cut,using the maximum flow algorithm through the shortest path of the dual graph of network flow graph,the Dijkstra algorithm is improved and an optimized Dijkstra algorithm model is proposed.The shortest path nodes are selected by utilizing the small root heap of heap sort in the improved algorithm.The nodes of heap are processed by using set computation.In this way,the nodes taking part in operations have been reduced,the efficiency of algorithm is increased.

关 键 词：最大流最小割 网络流图 对偶图 最短路径 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]