最短路问题的改进算法  

Improved algorithm for shortest-paths problem

作　　者：孙小军[1] 

机构地区：[1]宝鸡文理学院数学系,陕西宝鸡721013

出　　处：《计算机工程与设计》2009年第16期3762-3764,共3页Computer Engineering and Design

基　　金：陕西省自然科学基础研究计划基金项目(2006A12);宝鸡文理学院重点基金项目(ZK0829)

摘　　要：通过引入两个数组,从提高算法效率和增强寻路直观性两个方面对无回路网络最短路问题的权矩阵法进行了改进。改进后的算法既能快速的计算从源节点到其目的节点的最短路权又能更直观的找出最短路。最后算法分析和仿真结果表明,改进算法较权矩阵法相比,运算速度有了明显的提高,是计算无回路网络最短路的一种有效算法。The weight matrix method for finding shortest-paths in the network without circuit is improved, by applying two arrays to improve the efficiency of weight matrix method and enhance observation for finding shortest-paths in the network without circuit. The improved algorithm can both calculate shortest-path weights more quickly and find shortest paths more directly from source to destination, Finally, algorithm analysis and simulation results show that the computing speed of improved algorithm is improved a lot compared with the weight matrix method and it is an effective algorithm for finding shortest-paths in the network without circuit.

关 键 词：无回路网络 最短路 权矩阵 数组 

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