Horje

BRUTE force algorithm - Travelling Salesman - Algorithm
Learn
Algorithm - Travelling Salesman - Brute force algorithm
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.

 
Read Article
https://develop.horje.com/learn/1434/reference

 

Horje