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. In this tutorial paper, we describe 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. |
Year | DOI | Venue |
---|---|---|
1991 | 10.1007/BF02073941 | Annals OR |
Keywords | Field | DocType |
branch and bound,lower bound,optimization problem,shortest path,shortest path algorithm,recurrence relation | Discrete mathematics,Average path length,Mathematical optimization,Shortest path problem,Constrained Shortest Path First,Floyd–Warshall algorithm,Yen's algorithm,Shortest Path Faster Algorithm,Mathematics,Euclidean shortest path,K shortest path routing | Journal |
Volume | Issue | Citations |
33 | 5 | 0 |
PageRank | References | Authors |
0.34 | 3 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
E. L. Lawler | 1 | 1102 | 585.42 |