张柏礼 王媛瑗 洪 亮 田 伟 吕建华, 2

(1东南大学计算机科学与工程学院, 南京 211189)(2东南大学计算机网络和信息集成教育部重点实验室, 南京 211189)(3中国能源研究会电力安全与应急技术中心, 北京 100045)(4南京弘毅电气自动化有限公司, 南京 210039)

动态网络中最大流快速增量求解

张柏礼1,2王媛瑗1洪 亮3田 伟4吕建华1, 2

(1东南大学计算机科学与工程学院, 南京 211189)(2东南大学计算机网络和信息集成教育部重点实验室, 南京 211189)(3中国能源研究会电力安全与应急技术中心, 北京 100045)(4南京弘毅电气自动化有限公司, 南京 210039)

利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA-ART．算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算. 同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量．其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率．实验结果表明,MFIA-ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络．

最大流;增量算法;增广路径选……