Abstract: In this paper we are going to present a method that can help us to deal with several dynamic programming problems as optimal path problems in weighted digraphs, even problems which apparently don't have anything in common with graph theory. Furthermore, this approach makes possible such a classification of the dynamic programming strategies which can help in the comprehension of the essence of this programming technique.
Keywords: Dynamic programming, graph theory, optimal path algorithms.
Classification (MSC2000): 90C39; 49L20, 68R10, 05C12, 05C38
Full text of the article: