A new algorithm to find the k shortest paths
Chengjiang Li · Journal of Shandong University · 2006
A new algorithm is described to enumerate the k shortest paths connecting a given pair of vertices in a undirected graph.Our algorithm outputs the paths in order by length in total time O(m+nlogn+mlogk).The algorithm is bases on dynamic programming.Firstly compute the shortest distances for every vertex to the source,later trace to the source from the destination on the ground of the distance data and list the k shortest paths.