Learning On the Way

847. Shortest Path Visiting All Nodes

You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

DFS

def shortestPathLength(self, graph: List[List[int]]) -> int: 
    cache = {} # Will cause infitite loop if using @cache 
    def steps(node, status): 
        if (node, status) in cache: 
            return cache[node, status] 
        if status & (status - 1) == 0: 
            return 0 
        cache[node, status] = float('inf') # This is the key to avoid infinite loop 
        for neighbor in graph[node]: 
            if status & (1 << neighbor):  
                cache[node, status] = min(cache[node, status], 1 + steps(neighbor, status), 1 + steps(neighbor, status ^ (1 << node))) 
        return cache[node, status] 
    final_status = (1 << len(graph)) - 1 
    return min(steps(node, final_status) for node in range(len(graph)))

BFS

def shortestPathLength(self, graph): 
    if len(graph) == 1: 
        return 0 
     
    n = len(graph) 
    final_status = (1 << n) - 1 
    queue = collections.deque([(node, 1 << node) for node in range(n)]) 
    seen = set(queue) 
    steps = 1 
    while queue: 
        for _ in range(len(queue)): 
            node, status = queue.popleft() 
            for neighbor in graph[node]: 
                next_status = status | (1 << neighbor) 
                if next_status == final_status: 
                    return steps 
                 
                if (neighbor, next_status) not in seen: 
                    seen.add((neighbor, next_status)) 
                    queue.append((neighbor, next_status)) 
         
        steps += 1