一种基于改进堆优化Dijkstra算法的最小费用最大流算法

doi:10.3969/j.issn.1006-2475.2020.02.002

计算机与现代化

一种基于改进堆优化Dijkstra算法的最小费用最大流算法

(华南理工大学信息网络工程研究中心，广东广州510641)

收稿日期:2019-09-23 出版日期:2020-03-03 发布日期:2020-03-03
作者简介:邓国强（1984-），男，广东梅州人，工程师，硕士，研究方向：软件定义网络，E-mail: denggq@scut.edu.cn；通信作者：韩颖铮（1984-），女，高级工程师，硕士，研究方向：软件定义网络，网络安全，E-mail: hanyz@scut.edu.cn。
基金资助:
广东省重点领域研发计划项目（2019B010137001）；赛尔网络下一代互联网技术创新项目（NGII20180111）

A Minimum Cost Maximum Flow Algorithm Based on #br# Improved Heap Optimization Dijkstra Algorithm

(Information Network Engineering and Research Center, South China University of Technology, Guangzhou 510641, China)

Received:2019-09-23 Online:2020-03-03 Published:2020-03-03

摘要/Abstract

摘要： 通过最短路径算法在残存网络中搜索汇点的最小费用路径是流网络中求解最小费用最大流的主要方式，而Dijkstra算法是最高效的最短路径算法之一。本文通过证明残存网络中不存在负循环，采用改进的堆优化Dijkstra算法在残存网络中搜索最小费用路径以提升算法的效率。实验结果表明，与经典的基于最短路径快速算法的最小费用最大流算法和基于Bellman-Ford算法的最小费用最大流算法对比，本文提出的改进算法具有更高的时间效率。

关键词: 最小费用最大流, Dijkstra算法, 堆优化

Abstract: The minimum cost path for searching for sinks in the surviving network by the shortest path algorithm is the main way to solve the minimum cost maximum flow in the flow network, and the Dijkstra algorithm is one of the most efficient shortest path algorithms. In this paper, by demonstrating that there is no negative power circle in the surviving network, the improved heap optimization Dijkstra algorithm is used to search the remaining network for the minimum cost path to improve the efficiency of the algorithm. The experimental results show that compared with the classical minimum cost maximum flow algorithm based on the shortest path fast algorithm and the minimum cost maximum flow algorithm based on Bellman-Ford algorithm, the improved algorithm proposed in this paper has higher time efficiency.

Key words: , minnimum cost maximum flow； Dijkstra algorithm； heap optimization

中图分类号:

TP301.6

邓国强，韩颖铮. 一种基于改进堆优化Dijkstra算法的最小费用最大流算法 [J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2020.02.002.

DENG Guo-qiang, HAN Ying-zheng . A Minimum Cost Maximum Flow Algorithm Based on #br# Improved Heap Optimization Dijkstra Algorithm[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2020.02.002.

参考文献

［1］郝元卿,刘凯杰,李子涵,等. 基于MCMF动态网络流算法适应性应急疏散模型的分析与优化［J］. 通讯世界, 2019,26(6):255-256.
［2］赵璐阳,王丽娟,宋金凤. 基于最小费用最大流改进算法的多种交通方式开行方案协同优化研究［J］. 铁道运输与经济, 2019,41(3):6-11.
［3］肖白,王思莹,谷禹. 计及最大供电能力和最小联络建设费用的主变联络结构优化［J］. 电力系统保护与控制, 2017,45(24):9-16.
［4］洪玲玲. 最小费用最大流理论在救灾物资运输模型中的应用［J］. 企业导报, 2015(21):27.
［5］严庭玉,盛进路,邓玉涵,等. 集装箱码头装卸作业调度优化配置的研究［J］. 青岛远洋船员职业学院学报, 2016,37(1):22-26.
［6］陈晓旭,吴恒,吴悦文,等. 基于最小费用最大流的大规模资源调度方法［J］. 软件学报, 2017,28(3):598-610.
［7］陈友荣,周骏华,王章权,等. 基于最小费用最大流的无线多媒体传感网多路径路由算法［J］. 电信科学, 2014,30(12):55-63.
［8］雷苏娇,李俊,吴海博,等. 基于最小费用最大流理论的CCN多路径路由算法［J］. 科研信息化技术与应用, 2014,5(3):59-67.
［9］王军,田波,陈建平. 一种基于最小费用最大流理论的Ad hoc路由协议［J］. 科学技术与工程, 2012,12(30):7941-7946.
［10］马辰阳,温显斌. 基于拓扑结构的多摄像头网络协同跟踪机制［J］. 天津理工大学学报, 2019,35(3):17-23.
［11］DANTZIG G B. Application of the simplex method to a transportation problem［M］// Activity 〖JP3〗Analysis and Production and Allocation. John Wiley & Sons, 1951:359-373.
［12］韩颖铮,邓国强,陆以勤. 基于有效反向网络的最大流算法［J］. 通信学报, 2018,39(S1):179-183.
［13］火博丰,刁强强,葛云鹏,等. 最短增广路算法改进最大流问题运行时间证明的修正［J］. 青海师范大学学报(自然科学版), 2016,32(1):1-6.
［14］李秋锦,李晓瑄,李雅文. 解决最大流问题的Ford-Fulkerson标号算法［J］. 信息与电脑(理论版), 2019(10):32-35.
［15］孙小军,王志强,刘三阳. 网络最大流算法的性能分析［J］. 数学的实践与认识, 2013,43(17):120-124.
［16］赵礼峰,陶晓莉. 最小费用最大流问题的一种新算法［J］. 计算机技术与发展, 2014,24(1):130-132.
［17］赵礼峰,白睿,宋常城. 求解最小费用最大流的新方法［J］. 计算机技术与发展, 2012,22(5):94-96.
［18］程德文,吴育华. 求最小费用最大流的改进标号法［J］. 系统管理学报, 2009,18(2):237-240.
［19］唐四云,罗操,张倩. 最小费用最大流的改进算法［J］. 广东技术师范学院学报, 2019,40(3):10-14.
［20］CORMEN T H, LEISERSON C E, RIVEST R L, et al. 算法导论［M］.原书第3版. 北京:机械工业出版社, 2012:383-387,291-302.
［21］韩伟一,王铮. 负权最短路问题的新算法［J］. 运筹学学报, 2007(1):111-120.
［22］段凡丁. 关于最短路径的SPFA快速算法［J］. 西南交通大学学报, 1994(2):207-212.
［23］夏正冬,卜天明,张居阳. SPFA算法的分析及改进［J］. 计算机科学, 2014,41(6):180-184.

[1]	黄翼虎, 于亚楠. 基于改进Dijkstra算法的防冲突最短路径规划研究[J]. 计算机与现代化, 2022, 0(08): 20-24.
[2]	潘成浩,郭敏. 基于松弛Dijkstra算法的移动机器人路径规划[J]. 计算机与现代化, 2016, 0(11): 20-24.

一种基于改进堆优化Dijkstra算法的最小费用最大流算法

A Minimum Cost Maximum Flow Algorithm Based on #br# Improved Heap Optimization Dijkstra Algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价