| 基于固定序的Bellman-Ford算法的改进 |
| |
| 引用本文： | 韩伟一.基于固定序的Bellman-Ford算法的改进[J].运筹与管理,2015,24(4):111-115. |
| |
| 作者姓名： | 韩伟一 |
| |
| 作者单位： | 哈尔滨工业大学 经济与管理学院,黑龙江 哈尔滨 150001 |
| |
| 基金项目： | 国家自然科学基金资助项目(71101037);中央高校基本科研业务费专项资金资助(HIT.HSS.201406) |
| |
| 摘 要： | 固定序算法是Bellman-Ford算法的一种基本改进算法。为了改变固定序算法在稀疏图上的劣势,本文通过预先订制参与迭代的点的计算顺序,对该算法进行了改进。实验表明,在稀疏图上, 改进后的算法相对于原算法计算效率提高了近50%, 并能够与国际流行的先进先出算法相媲美。本文的工作表明,固定序算法不仅在大规模稠密图上具有明显的优势,而且在稀疏图上也具有很强的竞争力。
|
| 关 键 词： | 运筹学 固定序改进算法 最短路序 拓扑序Bellman-Ford算法 |
| 收稿时间： | 2013-06-27 |
Improvement of Bellman-Ford Algorithm Based on the Fixed Order |
| |
| HAN Wei-yi.Improvement of Bellman-Ford Algorithm Based on the Fixed Order[J].Operations Research and Management Science,2015,24(4):111-115. |
| |
| Authors: | HAN Wei-yi |
| |
| Institution: | School of Economic and Management, Harbin Institute of Technology, Harbin 150001, China |
| |
| 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. |
| |
| Keywords: | operations research improved fixed order algorithm the shortest path order topological order bellman-ford algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹与管理》浏览原始摘要信息 |
| 点击此处可从《运筹与管理》下载免费的PDF全文 |
