Traveling Salesman Problem Using Dynamic Programming | DAA

#sudhakaratchala #daavideos #dynamicprogramming
Let G=(V,E) be a directed graph with n vertices.
where V is set of vertices and E is set of edges
The edges are given along with their cost Cij where Cij 0 for all i,j

cost(i,j)= 0 if (i==j)
Cij if (i,j) ϵ E(G)
ꝏ if (i,j) ϵ E(G)

A tour for the graph G is directed cycle that includes every vertex exactly once, A tour starts at vertex ‘1’ and ends with vertex ’1’,but the remaining vertex are visited exactly once. The cost of the tour is sum of costs of edges on the tour.
Let g(i,S) be a length of the minimum shortest path, starting at vertex ‘i’ going through all the vertices in ‘s’ exactly once and terminating at vertex ‘i’.
g(i,S)=min{Cij + g(j, {S}-{j}}
jϵS
where S=V-{1}
If there are n vertices are there then (n-1)! Possible cycles can be formed. And maximum possible edges are 2n

Objective of the travelling sales person problem is to find the minimum shortest path/optimal solution.