Tutorial by Examples

A path through every vertex exactly once is the same as ordering the vertex in some way. Thus, to calculate the minimum cost of travelling through every vertex exactly once, we can brute force every single one of the N! permutations of the numbers from 1 to N. Psuedocode minimum = INF for all per...

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 c...