An efficient algorithm for k shortest simple paths
N Katoh, T Ibaraki, H Mine - Networks, 1982 - Wiley Online Library
N Katoh, T Ibaraki, H Mine
Networks, 1982•Wiley Online LibraryThis 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 (Kn3) time, since c (n …
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 (Kn3) time, since c (n …
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(Kn3) time, since c(n, m) ≤min[O(n2), O(m log n)] is known.
Wiley Online Library