Implementation and analysis of alternative algorithms for generalized shortest path problems (Q1086499)

This paper addresses a special class of deterministic dynamic programming problems which can be formulated as a generalized network problem. Because of the similarities between this class of dynamic programming problems and shortest path problems, we are naming it the generalized shortest path problem. A new primal extreme point algorithm and a new special dual algorithm are proposed here. While researchers have presented a variety of algorithms to solve this class of problems, there has been no computational analysis of these algorithms. An in-depth computational analysis is performed to determine the most efficient set of rules for implementing the algorithms of this paper.