Before we start learning the implementation of Travelling Salesman Problem in c, We need to understand the problem and its solution.

Travelling Salesman Problem algorithm description: There will be a set of cities given along with the distance between each of them. Here, the problem is to find out shortest route by visiting each city exactly once and return back to the starting city.

Consider below given Travelling Salesman Problem example to understand it step by step. Lets say there are four cities {A,B,C,D}. Let assume that each city is connected with every other city.

Here, the challenge is for a salesman to visit each city exactly once starting from city "A". we have assumed that salesman lives in the city "A" and will start travelling from city "A". After visiting all cities salesman will return back to the city "A".

There can be many possible optimal solutions. It is very hard to find an optimal solution for travelling salesman problem, because of that it is also known as NP-complete.

Brute force takes more time to compute the cost to solve TSP. Which means, we have to try all possible permutation combination. Then only we can find the route with the minimum cost. The time complexity for Brute force is O(!n) time, which is very slow.

To reduce this time complexity Dynamic Programming approach is used. Which solves travelling salesman problem in O(n^{^2}2^{^n)} time. Brute force is good for the small graph with a fewer number of nodes, but the dynamic programming approach is better when you have a larger graph.

Understand Travelling Salesman Problem Using Dynamic Programming

To understand the travelling salesman problem more effectively, consider the travelling salesman problem graph shown in the above image. Below is the matrix of the same graph example.

Travelling Salesman Problem matrix example

Consider "A" as a starting node. Next, compute and store the optimal value from A to each node {B, C, D}. Total (n-1)! possible ways to find the shortest route.

1. Consider city A as a starting and ending point.
2. Generate (n-1)! permutation for all cities (nodes)
3. Calculate the cost of every permutation and keep track of the minimum cost permutation
4. Return the permutation with minimum cost

Below mentioned is the dynamic equation for travelling salesman problem to find the shortest route.
 

To understand the above equation, we first need to understand each component of it. S is a subset of cities S ∈ {A, B, C, D}. g(i, S) represents the shortest path after visiting each node exactly once, staring from nodes A to D.

Let's understand it using a given graph and matrix step by step using an easy buy long method.

Travelling Salesman Problem (TSP) using dynamic programming

A -> B -> C -> D -> A
g(i , S) = min{ Cik + g(k, S - {k}) } = CAB + g(B, {C, D}) = CAB + CBC + g(C, {D}) = CAB + CBC + CCD + g(D, ∅) = CAB + CBC + CCD + CDA = 4 + 2 + 5 + 3 = 14

A -> B -> D -> C
g(i , S) = min{ Cik + g(k, S - {k}) } = CAB + g(B, {D, C}) = CAB + CBD + g(D, {C}) = CAB + CBD + CDC + g(C, ∅) = CAB + CBD + CDC + CCA = 4 + 1 + 5 + 1 = 11

A -> C -> B -> D
g(i , S) = min{ Cik + g(k, S - {k}) } = CAC + g(C, {B, D}) = C