| 带负权最短路问题前趋法的改进 |
| |
| 引用本文： | 孙小军,王志强. 带负权最短路问题前趋法的改进[J]. 安徽大学学报(自然科学版), 2009, 33(2) |
| |
| 作者姓名： | 孙小军 王志强 |
| |
| 作者单位： | 1. 宝鸡文理学院,数学系,陕西,宝鸡,721013
2. 国防科技大学,信息系统与管理学院,湖南,长沙,410073 |
| |
| 基金项目： | 陕西省科技厅自然科学基金，宝鸡文理学院重点项目 |
| |
| 摘 要： | 针对在带负权的有向网络中求最短路的前趋法的不足,结合动态规划思想从提高算法效率方面对其进行了改进,并提出了一种新算法.新算法通过引入变量记录当前节点到宿节点的最短路权,避免了前趋法中比较多条前趋路时反复计算最短路的冗余运算,同时弥补了动态规划不能直接求解带回路的有向网络最短路的缺陷,是一种计算带负权最短路问题的简便方法.该算法对非负权网络中的最短路问题同样有效.最后仿真结果和算例表明了新算法的有效性.
|
| 关 键 词： | 有向网络 负权 最短路 前趋法 动态规划 |
Improvement on method of forward graph for the shortest-paths problem |
| |
| SUN Xiao-jun,WANG Zhi-qiang. Improvement on method of forward graph for the shortest-paths problem[J]. Journal of Anhui University(Natural Sciences), 2009, 33(2) |
| |
| Authors: | SUN Xiao-jun WANG Zhi-qiang |
| |
| Affiliation: | 1.Department of Mathematics;Baoji College of Arts Science;Baoji 721013;China;2.College of Information System and Management;National University of Defense Technology;Changsha 410073;China |
| |
| Abstract: | To correct the shortcomings of the method of forward graph for solving the shortest-paths problem in directed network with negative weights,a new algorithm based on the idea of dynamic programming was presented,which was obtained by improving the efficiency of the method of forward graph.The new algorithm was convenient in calculating shortest-paths compared with the method of forward graph,since it avoided the redundancy calculation in comparing multi-forward paths.In the same time,the shortest-paths probl... |
| |
| Keywords: | directed networks negative weight shortest path method of forward graph dynamic programming |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
