#2.Write a program to perform Travelling Salesman Problem

from itertools import permutations

 
def calculate_path_distance(graph, path):
    distance = 0
    for i in range(len(path) - 1):
        distance += graph[path[i]][path[i + 1]]
    distance += graph[path[-1]][path[0]]  
    return distance

def tsp_brute_force(graph):
    
    cities = list(range(len(graph)))
    min_distance = float("inf")
    best_path = None

   
    for path in permutations(cities):
        current_distance = calculate_path_distance(graph, path)
        if current_distance < min_distance:
            min_distance = current_distance
            best_path = path

    return best_path, min_distance

# Example usage
# Define the graph as an adjacency matrix (distance between cities)
graph = [
    [0, 29, 20, 21],
    [29, 0, 15, 17],
    [20, 15, 0, 28],
    [21, 17, 28, 0]
]

best_path, min_distance = tsp_brute_force(graph)
print("Best Path:", best_path)
print("Minimum Distance:", min_distance)