# Dynamic Programming Algorithm

suggest change

Notice that if we consider the path (in order):

``(1,2,3,4,6,0,5,7)``

and the path

``(1,2,3,5,0,6,7,4)``

The cost of going from vertex `1` to vertex `2` to vertex `3` remains the same, so why must it be recalculated? This result can be saved for later use.

Let `dp[bitmask][vertex]` represent the minimum cost of travelling through all the vertices whose corresponding bit in `bitmask` is set to `1` ending at `vertex`. For example:

``````dp[12][2]

12   =   1 1 0 0
^ ^
vertices:   3 2 1 0``````

Since `12` represents `1100` in binary, `dp[12][2]` represents going through vertices `2` and `3` in the graph with the path ending at vertex 2.

Thus we can have the following algorithm (C++ implementation):

``````int cost[N][N];                        //Adjust the value of N if needed
int memo[1 << N][N];                   //Set everything here to -1
int cost = INF;
if (bitmask == ((1 << N) - 1)){      //All vertices have been explored
return cost[pos][0];             //Cost to go back
}
return memo[bitmask][pos];       //Just return the value, no need to recompute
}
for (int i = 0; i < N; ++i){         //For every vertex
if ((bitmask & (1 << i)) == 0){  //If the vertex has not been visited
cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);   //Visit the vertex
}
}
memo[bitmask][pos] = cost;           //Save the result
return cost;
}
//Call TSP(1,0)``````

This line may be a little confusing, so lets go through it slowly:

``cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);``

Here, `bitmask | (1 << i)` sets the ith bit of `bitmask` to 1, which represents that the ith vertex has been visited. The `i` after the comma represents the new `pos` in that function call, which represents the new “last” vertex. `cost[pos][i]` is to add the cost of travelling from vertex `pos` to vertex `i`.

Thus, this line is to update the value of `cost` to the minimum possible value of travelling to every other vertex that has not been visited yet.

Time Complexity

The function `TSP(bitmask,pos)` has `2^N` values for `bitmask` and `N` values for `pos`. Each function takes `O(N)` time to run (the `for` loop). Thus this implementation takes `O(N^2 * 2^N)` time to output the exact answer.