SOLVING SHORTEST ROUTE USING DYNAMIC PROGRAMMING PROBLEM
TADIOS KIROS KENEA *
Department of Mathematics, Arba Minch University, Ethiopia.
*Author to whom correspondence should be addressed.
Abstract
Dynamic programming is a technique that allows to break up the given problem in to a number of sub problems which is stages. At each stage there are a number of decision alternatives that is states. So the dynamic programming uses the idea of recursive equation to solve traveling salesman (a road network) problem using dynamic programming. The Traveling salesman (network) problem is one of the problem in mathematics and computer science which had drown attention as it is easy to understand and difficult to solve using forward and backward recursive equation. In this paper, researchers survey the various methods available to solve traveling salesman or network problem but analyze arrow drawing method to make critical evaluation of their time complexities. Hence using arrow drawing method to computing the shortest and longest path between two given locations in a road network is an important and simplest way to find applications in various map services. An implementation of the traveling salesman or a road network problem using dynamic programming is presented in this paper which generates optimal answer.
Keywords: Arrow drawing method, dynamic programming, network, operation research, recursion equation.