A note on shortest path problems with forbidden paths

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.