This lesson's interactive features are locked, please to keep using them

TSP Review

Consider the TSP algorithms that we wrote:

Solving TSP

def tsp(cities: list[int], paths: list[list[int]], dist: int) -> bool:
    perms = permutations(cities)
    for perm in perms:
        total_dist = 0
        for i in range(1, len(perm)):
            total_dist += paths[perm[i - 1]][perm[i]]
        if total_dist < dist:
            return True
    return False

Verifying TSP

def verify_tsp(paths: list[list[int]], dist: int, actual_path: list[int]) -> bool:
    total = 0
    for i in range(len(actual_path)):
        if i != 0:
            total += paths[actual_path[i - 1]][actual_path[i]]
    return total < dist