求解无环K短路径的Dijkstra算法

摘要

This article aims to-make some improvements on the basis of the improved Dijkstm algorithm that solves the K-shortest paths by the use of many labels on each node of a network, bring in two precursor node matrices pre and Kpre, the current path from the original node to the current node can be gained by means of the two matrices, then judge that whether this path is loopless, so that we can avoid loop appears in the process of the K-shortest paths finding, it turns out that the improved algorithm can find out the K-shortest paths, and it only needs less extra calculation amount, so it still keep a polynomial complexity of the original algorithm. Then numerical examples in different scale network are given to check the correctness and the effectiveness of the improved algorithm.%对多个标号的求解K短路径的Dijkstra改进算法进行完善，引入两个前驱节点矩阵pre和Kpre，通过这两个矩阵可以求出起始点到当前节点的当前路径，并判断这条路径是否有环，从而在寻找K短路的过程中避免了环的出现，完善后的算法可以求出前K短无环路径，该算法仅需要较少的额外计算量，所以仍然保持了算法的多项式复杂性．然后在不同规模的网络上对完善后的算法进行数值试验，验证了算法的正确性和有效性．