Premium
A note on shortest path problems with forbidden paths
Author(s) -
Smith Olivia J.,
Savelsbergh Martin W.P.
Publication year - 2014
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.21541
Subject(s) - k shortest path routing , shortest path problem , time complexity , longest path problem , path (computing) , yen's algorithm , set (abstract data type) , euclidean shortest path , shortest path faster algorithm , mathematics , combinatorics , floyd–warshall algorithm , dynamic programming , computer science , polynomial , algorithm , mathematical optimization , graph , dijkstra's algorithm , mathematical analysis , programming language
We consider the variant of the shortest path problem in which a given set of paths is forbidden to occur as a subpath in an optimal path. We establish that the most‐efficient algorithm for its solution, a dynamic programming algorithm, has polynomial time complexity; it had previously been conjectured that the algorithm has pseudo‐polynomial time complexity. Furthermore, we show that this algorithm can be extended, without increasing its time complexity, to handle non elementary forbidden paths. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 239–242 2014