travelling_salesman_problem.py

# -*- coding: utf-8 -*-
"""travelling_salesman_problem.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1TK4ZCtjDWLimJz_zHtpZp1VaeW0ivuSi
"""

from sys import maxsize
from itertools import permutations

def travellingSalesmanProblem(graph, s):
    V = len(graph)

    # store all vertex apart from source vertex
    vertex = []
    for i in range(V):
        if i != s:
            vertex.append(i)

    # store minimum weight Hamiltonian Cycle
    min_path = maxsize
    next_permutation = permutations(vertex)
    for i in next_permutation:
        # store current Path weight(cost)
        current_pathweight = 0

        # compute current path weight
        k = s
        for j in i:
            current_pathweight += graph[k][j]
            k = j
        current_pathweight += graph[k][s]

        # update minimum
        min_path = min(min_path, current_pathweight)

    return min_path

# Driver Code
if __name__ == "__main__":
    V = int(input("Enter the number of vertices: "))

    # Initialize the graph with zeros
    graph = [[0] * V for _ in range(V)]

    # Get the graph weights from the user
    for i in range(V):
        for j in range(V):
            graph[i][j] = int(input(f"Enter the weight between vertex {i} and {j}: "))

    source_vertex = int(input("Enter the source vertex: "))

    print(travellingSalesmanProblem(graph, source_vertex))