Travelling Salesperson using DP in Python

TSP.py

import sys
INFINITY = sys.maxsize

def travelling_salesperson_problem(weight, n, i, unvisited_cities):
    if(len(unvisited_cities) == 0):
        # If no cities left to traverse return to starting city 1
        # Assumption we always start and end tour at city 1
        dp[i][tuple()] = weight[i-1][0]
        return weight[i-1][0]
    
    # If this subproblem is already solved, lookup answer from stored table dp
    if tuple(unvisited_cities) in dp[i]:
        return dp[i][tuple(unvisited_cities)]
    
    min_cost = INFINITY
    # Traverse all cities and take minimum cost
    for j in list(unvisited_cities):
        next_unvisited_cities = list(unvisited_cities)
        next_unvisited_cities.remove(j)
        
        # Recurrence relation for TSP
        cost = weight[i-1][j-1] + travelling_salesperson_problem(weight, n, j, next_unvisited_cities)
        if(cost<min_cost):
            min_cost = cost
        
        
    #Store answer for current subproblem in dp table
    dp[i][tuple(unvisited_cities)] = min_cost
    return min_cost
    


print("Enter no of cities: ")
n = int(input())
print("Enter adjacency matrix: ")
weight = []
for i in range(n):
    weight.append([int(x) for x in input().split()])

dp = [dict() for x in range(n+1)]
unvisited_cities = list([x for x in range(2, n+1)])

min_cost = travelling_salesperson_problem(weight, n, 1, unvisited_cities)
# For looking up answers of subproblem
[print(x) for x in dp]
print("Min Cost:", min_cost)
    
    
"""
5
0 24 11 10 9
8 0 2 5 11
26 12 0 8 7
11 23 24 0 6
5 4 8 11 0    
"""