Brute Force Algorithm
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
minimum = INF for all permutations P current = 0 for i from 0 to N-2 current = current + cost[P[i]][P[i+1]] <- Add the cost of going from 1 vertex to the next current = current + cost[P[N-1]][P] <- Add the cost of going from last vertex to the first if current < minimum <- Update minimum if necessary minimum = current output minimum
N! permutations to go through and the cost of each path is calculated in
O(N), thus this algorithm takes
O(N * N!) time to output the exact answer.