Travelling Salesman Python Implementation Backtracking

travelling_salesman.py

# Given a starting vertex visit all vertex

from typing import Dict, Set


class Graph:
    def __init__(self):
        self.edges = list()
        self.graph: Dict[int, Set] = dict()
        self.visited = dict()
        self.salesman_start = None

    def make_graph(self, _edges) -> None:
        self.edges.extend(_edges)

        for u, v, w in self.edges:
            if u not in self.graph:
                self.graph[u] = set()

            self.graph[u].add((v, w))

    def refresh_visited(self):
        for node in self.graph:
            self.visited[node] = False

    def get_edge(self, u, v):
        for _v, w in self.graph.get(u, []):
            if _v == v:
                return w

    def all_nodes_are_visited(self):
        return False not in self.visited.values()

    def min_cost_to_visit_everything(self, start, edge_cost):
        self.visited[start] = True

        if self.all_nodes_are_visited() and self.get_edge(start, self.salesman_start) is not None:
            return edge_cost

        candidates = []

        for node, weight in self.graph[start]:
            if self.visited[node] is True:
                continue
            res = self.min_cost_to_visit_everything(start=node, edge_cost=weight)
            if res is not None:
                candidates.append(edge_cost + res)

        self.visited[start] = False
        return min(candidates) if candidates else None


if __name__ == '__main__':
    edges = [
        (1, 2, 16), (1, 3, 11), (1, 4, 6),
        (2, 1, 8), (2, 3, 13), (2, 4, 16),
        (3, 1, 4), (3, 2, 7), (3, 4, 9),
        (4, 1, 5), (4, 2, 12), (4, 3, 2)
    ]
    graph = Graph()
    graph.make_graph(_edges=edges)
    graph.refresh_visited()
    graph.salesman_start = 1
    min_cost = graph.min_cost_to_visit_everything(start=graph.salesman_start, edge_cost=0)
    print(min_cost)