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

Improved Matrix Iterative Label Algorithm for the Shortest Path Problem

最短路径模型是图论研究中的经典问题,针对传统的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.