改进的最短路径矩阵迭代标号法  

Improved Matrix Iterative Label Algorithm for the Shortest Path Problem

作　　者：薛瑞[1] 黄式东 潘虹[2] 

机构地区：[1]信阳师范学院计算机与信息技术学院,信阳464000 [2]信阳师范学院数学与信息科学学院,信阳464000

出　　处：《现代计算机（中旬刊）》2015年第9期3-6,35,共5页Modern Computer

基　　金：国家自然科学基金青年基金(No.11211400);河南省自然科学基金研究项目(No.142300410393)

摘　　要：最短路径模型是图论研究中的经典问题,针对传统的Dijkstra算法的不足,提出改进的矩阵迭代标号法。改进算法不仅可以有效地求解负权值最短路径问题,而且当两点间存在多条最短路径时,改进算法可以同时得到所有的最短路径。实验结果表明,改进算法的时间复杂度低于传统的Dijkstra算法,且算法简单、易于实现。The shortest path model is a classical problem in graph theory, aiming at the shortage of the traditional Dijkstra algorithm, proposes a ma-trix iterative label algorithm. The Improved algorithm can not only effectively solve the negative weight shortest path problem, and when there are exist multiple shortest paths between two points, the improved algorithm can also get all the shortest paths. Experimental results show that, the improved algorithm has lower time complexity than the traditional Dijkstra algorithm, and the algorithm is simple and easy to implement.

关 键 词：DIJKSTRA算法 最短路径 矩阵算法 

分 类 号：O157.5[理学—数学]