基于固定序的Bellman-Ford算法的改进

doi:10.12005/orms.2015.0127

运筹与管理 ›› 2015, Vol. 24 ›› Issue (4): 111-115.DOI: 10.12005/orms.2015.0127

基于固定序的Bellman-Ford算法的改进

韩伟一

哈尔滨工业大学经济与管理学院,黑龙江哈尔滨 150001

收稿日期:2013-06-27 出版日期:2015-08-12
作者简介:韩伟一(1974-),男,讲师,硕士生导师。
基金资助:
国家自然科学基金资助项目(71101037);中央高校基本科研业务费专项资金资助(HIT.HSS.201406)

Improvement of Bellman-Ford Algorithm Based on the Fixed Order

HAN Wei-yi

School of Economic and Management, Harbin Institute of Technology, Harbin 150001, China

Received:2013-06-27 Online:2015-08-12

摘要/Abstract

摘要： 固定序算法是Bellman-Ford算法的一种基本改进算法。为了改变固定序算法在稀疏图上的劣势,本文通过预先订制参与迭代的点的计算顺序,对该算法进行了改进。实验表明,在稀疏图上, 改进后的算法相对于原算法计算效率提高了近50%, 并能够与国际流行的先进先出算法相媲美。本文的工作表明,固定序算法不仅在大规模稠密图上具有明显的优势,而且在稀疏图上也具有很强的竞争力。

关键词: 运筹学, 固定序改进算法, 最短路序, 拓扑序Bellman-Ford算法

Abstract: The fixed order algorithm is one of basic improved algorithms on the classic Bellman-Ford algorithm. In view of its inferiority in the sparse directed graph, the algorithm is improved by presenting the computational order of vertices in advance. The experiments show that the improved algorithm is faster than the original one by 50% in the sparse directed graph approximately. Moreover, it is compared with the FIFO algorithm, which is the most attractive basic improved algorithm of Bellman-Ford algorithm at present. It means that the fixed order algorithm is very competitive in both the large-scale dense directed graph and the sparse directed graph.

Key words: operations research, improved fixed order algorithm, the shortest path order, topological order, bellman-ford algorithm

中图分类号:

O221.7

韩伟一. 基于固定序的Bellman-Ford算法的改进[J]. 运筹与管理, 2015, 24(4): 111-115.

HAN Wei-yi. Improvement of Bellman-Ford Algorithm Based on the Fixed Order[J]. Operations Research and Management Science, 2015, 24(4): 111-115.

参考文献

[1] 韩伟一,王铮.负权最短路问题的新算法[J].运筹学学报,2007,11(1):111-120.
[2] 韩伟一.经典Bellman-Ford算法的改进及其实验评估[J].哈尔滨工业大学学报,2012,44(7):74-77.
[3] Bellman R E. On a routing problem[J]. Quarterly of applied mathematics, 1958, 16(1): 87-90.
[4] Glover F, Klingman D, Phillips N V. A new polynomially bounded shortest path algorithm[J]. Operations research,1985, 33(1): 65-72.
[5] Glover F, Klingman D, Phillips N V, Schneider R F. New polynomial shortest path algorithms and its computational attributes[J]. Management science, 1986, 31: 1106-1128.
[6] Goldberg A V, Radzik T. A heuristic improvement of the bellman-ford algorithm[J]. Applied Mathematics letters,1993, 6(3): 3-6.
[7] Tarjan R E. Shortest paths[R]. AT&T Bell Laboratories, Murray Hill, 1981.
[8] Yen J Y. An algorithm for finding shortest routes from all source nodes to a given destination in general networks[J]. Quarterly of applied mathematics, 1970, 27: 526-530.
[9] 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报,1994,29(2):202-212.
[10] Cherkassky B V, Georgiadis L, Goldberg A V, Tarjan R E, Werneck R F. Shortest-path feasibility algorithm: an experimental evaluation[J]. ACM Journal of experimental algorithmics, 2009, 14(2.7): 1-37.
[11] Hung M S, Divoky J J. A computational study of efficient shortest path algorithms[J]. Computer & Operations research, 1988, 15(6): 567-576.
[12] Lewanddowski S. Shortest paths and negative cycle detection in graphs with negative weights[R]. Stuttgart University, 2010.
[13] Cherkassky B V, Goldberg A V. Negative-cycle detection algorithm[J]. Mathematical programming, 1999, 85: 277-311.
[14] Cherkassky B V, Goldberg A V. Shortest paths algorithms: theory and experimental evaluation[J]. Mathematical programming, 1996, 73: 129-174.

[1]	汪洪涛, 张翔, 王珂. 1996~2017年《Operations Research》期刊发文统计分析[J]. 运筹与管理, 2020, 29(2): 229-239.
[2]	王诺, 丁凯, 吴迪, 吴暖. 面向远海岛礁群的双向物流网络规划[J]. 运筹与管理, 2019, 28(6): 118-128.
[3]	陈江涛, 吕建秋. 基于知识图谱的运筹学发展现状及趋势研究[J]. 运筹与管理, 2019, 28(1): 194-199.
[4]	张萌,王能民. 重大事故规避的危险品运输车辆路径优化研究[J]. 运筹与管理, 2018, 27(8): 1-9.
[5]	高沛然, 张金隆, 艾学轶, 李明, 马自香. PLS-DEMATEL方法及其应用研究——以组织敏捷性的IT影响因素分析为例[J]. 运筹与管理, 2018, 27(3): 126-132.
[6]	郭小威, 李保刚, 滕克难. 基于可用度的复杂结构装备检修时机决策模型[J]. 运筹与管理, 2018, 27(2): 11-14.
[7]	董锋, 树琳, 李靖云, 乔均. 产学研协同创新效率及提升路径研究[J]. 运筹与管理, 2018, 27(10): 185-192.
[8]	张源凯, 孙丽君, 胡祥培. 成品油配送多车舱车辆指派及路径优化问题研究[J]. 运筹与管理, 2017, 26(7): 1-9.
[9]	包晓光, 刘朝晖, 余炜. 线形网络上单台车辆分群调度问题[J]. 运筹与管理, 2017, 26(5): 125-129.
[10]	王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017, 26(4): 70-75.
[11]	韩伟一. 一种基于虚拟决策单元的排序方法的完善和扩展[J]. 运筹与管理, 2017, 26(11): 65-69.
[12]	薄洪光,张鑫,潘裕韬. 混合无等待流水线干扰管理调度方法研究[J]. 运筹与管理, 2016, 25(3): 246-254.
[13]	汪芸芳,陈丽华. 城市化进程中地铁晚高峰经济出行模式分析[J]. 运筹与管理, 2016, 25(2): 138-142.
[14]	薛克雷,潘郁,潘芳,钱存华. 云环境下面向复杂资源需求的虚拟机能效部署研究[J]. 运筹与管理, 2016, 25(2): 143-150.
[15]	崔玮,王三银. 城市非农用地碳排放驱动因素的PDA模型[J]. 运筹与管理, 2016, 25(2): 156-164.

基于固定序的Bellman-Ford算法的改进

Improvement of Bellman-Ford Algorithm Based on the Fixed Order

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics