Finding a short hamiltonian path using the nearest neighbor algorithm

nearest_neighbor.py

def find_short_hamiltonian_path(origin, nodes, costs, dependencies):
    current_node = origin
    visited_nodes = set([origin])
    remaining_nodes = nodes - visited_nodes
    path = [origin]

    while len(remaining_nodes) > 0:
        smallest_cost = float('inf')

        for node in remaining_nodes:
            if not is_valid_extension(visited_nodes, node, dependencies):
                continue
                
            if costs[current_node][node] < smallest_cost:
                closest_node = node
                smallest_cost = cost

        path.append(closest_node)
        remaining_nodes.remove(closest_node)
        visited_nodes.add(closest_node)
        current_node = closest_node

    return path

def is_valid_extension(visited_nodes, new_node, dependencies):
    if dependencies.get(new_node) and dependencies.get(new_node) not in visited_nodes:
        return False

    return True