C program of Travelling Salesman Problem : The Travelling salesman problem (TSP) is an NP-hard problem. NP-hard problem is a class of problems that are, informally, “at least as hard as the hardest problems in NP” or you can simply say solution to problem cannot be generalized i.e. We may not have optimal solution every time.
I have tried to find the solution using operational search technique but its not always optimal. :D Its not mine approach, all the approaches for this problem cannot guarantee an optimal solution every time but i can simply say it will going to be the best approach for solving Travelling salesman problem other than neural networks approach, genetic algorithm and dynamic programming.

Algorithm to solve Travelling Salesman Problem :

1. Prepare a cost matrix to calculate the weights . If the entered cost matrix is not a square matrix then add a new column with zero cost element.
2. Determine the minimum element in each row and subtract the minimum element in each row from all the elements of the respective rows.
3. Now we have a resulting matrix. Now repeat the same process of step 2 for all the columns i.e. determine the minimum element in each column and subtract that minimum value from all elements of their respective column to obtain new resulting matrix.

4. Now after row and column operations, draw minimum number of horizontal and vertical lines to cover all zeros in resulting matrix. Let a be the minimum number of lines and n is the order of matrix.

Then two possible scenarios can happen :
4.1 If a=n,then an optimal assignment of paths can be done.
4.2 If N<n,then proceed.

5. Now find smallest uncovered element in the matrix by “a” lines.

6. Subtract the minimum element obtained in step 5 from all uncovered elements and add the same elements at the intersection of horizontal and vertical lines to obtain intermediate matrix.
7. Repeat step(2) to step (4) until we get the case 4.1 .
8. (For making zero assignments) Examine the rows successively row by row until single zero is found. Circle this zero to make the assignment and then mark a cross(x) over all zeros if its lying in the column of the circled zero, showing that they can’t be considered for future assignment. Continue in this manner until all the zeros have been examined.
Repeat the same procedure for columns also.
9. Repeat the step 7 successively until one of the below condition arises :
(i) If no unmarked zeros is left,then the process ends
(ii) If there lies more than one of the unmarked zero in any column or row then, circle one of the unmarked zeros arbitrarily and mark a cross in the cell of remaining zeros in its row or column and repeat the process until no unmarked zero is left in the matrix.
10 :- Thus exactly one marked circled zero in each row and each column of the matrix is obtained and hence assignment corresponding to these marked circle zeros will give the optimal assignment.

That ends the algorithm for Travelling Salesman Problem. Now lets see C program of Travelling Salesman Problem Solution.