Algorithms Traveling Salesman suggest change

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

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents