带负权最短路问题前趋法的改进  

Improvement on method of forward graph for the shortest-paths problem

作　　者：孙小军[1] 王志强[2] 

机构地区：[1]宝鸡文理学院数学系,陕西宝鸡721013 [2]国防科技大学信息系统与管理学院,湖南长沙410073

出　　处：《安徽大学学报（自然科学版）》2009年第2期27-30,共4页Journal of Anhui University(Natural Science Edition)

基　　金：陕西省科技厅自然科学基金资助项目(2006A12);宝鸡文理学院重点项目(zk0829)

摘　　要：针对在带负权的有向网络中求最短路的前趋法的不足,结合动态规划思想从提高算法效率方面对其进行了改进,并提出了一种新算法.新算法通过引入变量记录当前节点到宿节点的最短路权,避免了前趋法中比较多条前趋路时反复计算最短路的冗余运算,同时弥补了动态规划不能直接求解带回路的有向网络最短路的缺陷,是一种计算带负权最短路问题的简便方法.该算法对非负权网络中的最短路问题同样有效.最后仿真结果和算例表明了新算法的有效性.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 avoided the redundancy calculation in comparing multi-forward with the method of forward graph, since it paths. In the same time, the shortest-paths problem in directed networks with circuits could be solved by the algorithm. It was also effective for shortest - paths problem in network without negative weight. Simulation results and example showed the effectiveness of the new algorithm.

关 键 词：有向网络 负权 最短路 前趋法 动态规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]