python_tsp.py

# TSP with heuristic dynamic programming
# Solution is based on "always picking the shortest route available" on the matrix

from itertools import permutations


def travel_salesman_problem(graph: list, path_sum: int = 0) -> int:
    vertex = []
    min_path = []
    
    for i in range(len(graph)):
        if i != path_sum:
            vertex.append(i)
            
    next_permutation = permutations(vertex)
    
    for i in next_permutation:
        current_pathweigth = 0
        
        k = s
        
        for j in i:
            current_pathweigth += graph[k][j] 
            k = j
        current_pathweigth += graph[k][s]
        min_path.append(current_pathweigth)
        x = sorted(min_path)
        
    return x[0]

graph = [[0, 10, 15, 20],
         [10, 0, 35, 25],
         [15, 35, 0, 30],
         [20, 25, 30, 0]]

path_sum = 0

travel_salesman_problem(graph, path_sum)