travelling-salesman-problem.py

from sys import maxsize 
# Count of total vertices in graph
V = 4

def travellingSalesmanProblem(graph, s): 

    vertex = [] 
    for i in range(V): 
        if i != s: 
            vertex.append(i) 

    min_path = maxsize 

    while True: 

        weight = 0

        current = s 
        for i in range(len(vertex)): 
            weight += graph[current][vertex[i]] 
            current = vertex[i] 
        weight += graph[current][s] 

        min_path = min(min_path, weight) 

        if not step(vertex): 
            break

    return min_path 

def step(vertex): 

    n = len(vertex) 

    i = n - 2
    while i >= 0 and vertex[i] >= vertex[i + 1]: 
        i -= 1

    if i == -1: 
        return False

    j = i + 1
    while j < n and vertex[j] > vertex[i]: 
        j += 1
    j -= 1

    vertex[i], vertex[j] = vertex[j], vertex[i] 

    left = i + 1
    right = n - 1

    while left < right: 
        vertex[left], vertex[right] = vertex[right], vertex[left] 
        left += 1
        right -= 1

    return True

if __name__ == "__main__": 

    # Adjacency List
    graph = [[0, 10, 15, 20], [10, 0, 35, 25], 
            [15, 35, 0, 30], [20, 25, 30, 0]]
    s = int(input("Please enter the starting vertex: "))
    print(travellingSalesmanProblem(graph, s-1))