Technical Note—Determining All Optimal and Near-Optimal Solutions when Solving Shortest Path Problems by Dynamic Programming

DOI10.1287/opre.32.6.1381zbMath0553.90101OpenAlexW2015035116MaRDI QIDQ3216467

Michael S. Waterman, Thomas H. Byers

Publication date: 1984

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.32.6.1381

zbMATH Keywords

depth-first searchshortest path problemsnear-optimal policiesall solutionsstacking techniques

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Dynamic programming (90C39)

Related Items

Parametric and ensemble sequence alignment algorithms ⋮ Enumerating \(K\) best paths in length order in DAGs ⋮ On modelling and solving the shortest path problem with evidential weights ⋮ Optimization problems with evidential linear objective ⋮ A stochastic programming approach for Shelter location and evacuation planning ⋮ Distance confined path problem and separable integer programming ⋮ Finding the k Shortest Paths ⋮ General methods of sequence comparison ⋮ RNA secondary structures and their prediction ⋮ A dynamic programming algorithm to find all solutions in a neighborhood of the optimum ⋮ Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions