Computing shortest paths in networks derived from recurrence relations

Computing shortest paths in networks derived from recurrence relations

0.00 Avg rating0 Votes
Article ID: iaor19921107
Country: Switzerland
Volume: 33
Start Page Number: 363
End Page Number: 377
Publication Date: Oct 1991
Journal: Annals of Operations Research
Authors:
Keywords: programming: dynamic
Abstract:

Dynamic programming formulations of optimization problems often call for the computation of shortest paths in networks derived from recurrence relations. These derived networks tend to be very large, but they are also very regular and lend themselves to the computation of nontrivial lower bounds on path lengths. This tutorial paper describes unidirectional and bidirectional search procedures that make use of bounding information in computing shortest paths. When applied to many optimization problems, these shortest path algorithms capture the advantages of both dynamic programming and branch-and-bound.

Reviews

Required fields are marked *. Your email address will not be published.