An efficient algorithm for K shortest simple paths

Abstract

Abstract This article gives an efficient algorithm for obtaining K shortest simple paths between two specified nodes in an undirected graph G with non‐negative edge lengths. Letting n be the number of nodes and m be the number of edges in G , its running time is O ( Kc ( n, m )) if the shortest paths from one node to all the other nodes are obtained in c (n, m) [≥ O ( m )] time, and the required space is O ( Kn + m ). This time bound is better than those realized by existing algorithms, the best of which, proposed by Yen, requires O ( Kn 3 ) time, since c ( n, m ) ≤min[ O ( n 2 ), O ( m log n )] is known.