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

Thomas H. Byers and Michael S. Waterman
Additional contact information
Thomas H. Byers: Digital Research Inc., Monterey, California
Michael S. Waterman: University of Southern California, Los Angeles, California

Operations Research, 1984, vol. 32, issue 6, 1381-1384

Abstract: This paper presents a new algorithm for finding all solutions with objective function values in the neighborhood of the optimum for certain dynamic programming models, including shortest path problems. The new algorithm combines the depth-first search with stacking techniques of theoretical computer science and principles from dynamic programming to modify the usual backtracking routine and list all near-optimal policies. The resulting procedure is the first practical algorithm for a variety of large problems that are of interest.

Keywords: 111; near-optimal; policies (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.6.1381 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:6:p:1381-1384

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().