Portal de Periódicos da CAPES

An efficient algorithm for K shortest simple paths

1982; Wiley; Volume: 12; Issue: 4 Linguagem: Inglês

10.1002/net.3230120406

1097-0037

Naoki Katoh, Toshihide Ibaraki, Hisashi Mine,

Data Management and Algorithms

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.