K-shortest Loopless Path Finding on the Basis of Improved Dijkstra Algorithm
Zhao Jian · Journal of Huaiyin Teachers College · 2012
This article aims to make some improvements on the basis of the improved Dijkstra 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.