Optimization of Dynamic Programming Technique for Travelling Salesman Problem

Travelling Salesman Problem (TSP) is a problem where an optimal path has to be calculated from source city to destination. Optimality of the path generally refers to the minimum cost (distance) between source and destination. In the proposed methodology, multiple optimal paths are calculated which not only provides the user an optimal path, but it also provides the user choice to select an optimal path from the list of multiple optimal paths having same source and destination, but different cities pattern in between them using dynamic programming. The proposed methodology has been compared with the branch and bound approach of solving TSP, and the proposed methodology came out to be faster than the latter approach, and also it provides the multiple optimal paths to the user which is not provided by any other approach.