Premium
An efficient algorithm for K shortest simple paths
Author(s) -
Katoh N.,
Ibaraki T.,
Mine H.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120406
Subject(s) - combinatorics , shortest path problem , shortest path faster algorithm , simple (philosophy) , floyd–warshall algorithm , running time , undirected graph , mathematics , time complexity , binary logarithm , yen's algorithm , k shortest path routing , graph , node (physics) , enhanced data rates for gsm evolution , algorithm , computer science , dijkstra's algorithm , physics , telecommunications , philosophy , epistemology , quantum mechanics
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.