Font Size: 

We present a new algorithm for enumerating the $k$ shortest simple (loopless) paths in nondecreasing order between a designated pair of vertices in a given undirected graph. Our algorithm is based on $A^{*}$ algorithm and uses Dijkstra's algorithm to estimate the cost to rich the destination node. The algorithm calls Dijkstra's algorithm only ones and uses obtained values for generating candidates for next path. It also uses efficient method for detecting loops in subpaths to early prune inadmissible paths with loops. Some experimental results for different types of graphs are provided to illustrate the efficiency and applicability of the algorithm.

Algorithms, $k$ shortest paths, $A^{*}$ algorithm, Dijkstra's algorithm, Weighted undirected graphs