摘要
目前在不含负回路的网络中,对于求解任意两节点之间最短路问题的方法有很多,Floyd算法是最经典的算法之一,但随着节点数量的增加,重复的计算量也随之增大,从而降低了计算效率。为此,文中通过迭代矩阵和下标标注法对Floyd算法进行了改进,改进后的算法既能快速地计算出网络中任意两节点之间的最短路长值,又能更直观地找出最短路径。通过具体实例分析表明,Floyd改进算法减少了重复计算,简化了路径标注方法,提高了计算效率。
At present,there are many algorithms for solving the shortest path between any two points in the network without negative loop. Floyd algorithm is one of the most classical algorithms. But when the number of nodes increases,the amount of repeated calculation also increases which reduces the efficiency of the algorithm. Floyd algorithm is improved in this paper by using iterative matrix and subscript tagging method. The improved algorithm not only can calculate the shortest path weights more quickly but also find shortest paths more directly. The specific instance analysis indicates that the improved algorithm reduces the repeated calculation and simplifies the path tagging method,which lead to the improvement of the computational efficiency.
出处
《计算机技术与发展》
2014年第8期31-34,共4页
Computer Technology and Development
基金
国家自然科学基金资助项目(61070234
61071167)
关键词
最短路
不含负回路网络
Floyd改进算法
迭代矩阵
the shortest path
network without negative loop
improved Floyd algorithm
iterative matrix
