# Brute Force Algorithm

suggest changeA 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 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[0]] <- Add the cost of going from last vertex to the first
if current < minimum <- Update minimum if necessary
minimum = current
output minimum
```

**Time Complexity**

There are `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.

Found a mistake? Have a question or improvement idea?
Let me know.

Table Of Contents