基于有效反向网络的最大流算法  

Maximum flow algorithm based on effective reverse network

作　　者：韩颖铮[1] 邓国强[1] 陆以勤[1] HAN Yingzheng;DENG Guoqiang;LU Yiqin(Network Research Center,South China University of Technology,Guangzhou 510641,China)

机构地区：[1]华南理工大学信息网络工程研究中心,广东广州510641

出　　处：《通信学报》2018年第A01期179-183,共5页Journal on Communications

基　　金：广东省省级科技计划基金资助项目(No.2015A030401027)~~

摘　　要：针对经典的最大流Dinic算法反复沿着无效路径搜索造成的时间浪费问题,提出了一种基于有效反向网络的最大流算法。算法修改了汇点的深度定义,在计算节点深度过程中构建了有效反向网络,从汇点出发搜索增广路径,降低了节点深度计算的次数,同时避免了反复搜索无效路径。实验结果表明,基于有效反向网络的最大流算法的求解速度优于Dinic算法。In the classical max flow Dinic algorithm,repeated search along the invalid path causes time wastage.A maximum flow algorithm based on effective reverse network was proposed.The algorithm modified the depth definition of the sink point,constructed an effective reverse network in the process of calculating the node depth,and searched for the augmented path from the sink point.The times of node depth calculations is reduced,and the repeated searches along invalid paths is avoided.The experimental results show that the maximum flow algorithm based on effective reverse network in time performance has a greater advantage than Dinic algorithm.

关 键 词：最大流 流网络 有效反向网络 最短增广链 

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