Travelling salesperson problem

Travelling Salesman problem is used to find shortest distance.If a person give group of cities and ask us to find a particular city with shortest distance in this situation Travelling Salesman Problem will help us to find shortest distance of the city.

Travelling salesman problem is the too bad computational problem. We can also use brute-force approach to evaluate every possible route and select the best one. For n number of vertices in a graph, there are (n - 1)! number of possibilities.

Algorithm: Traveling-Salesman-Problem 
T{1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      T(S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      T(S, j) = min {T (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj T({1, 2, 3, …, n}, j) + d(j, i)