847. Shortest Path Visiting All Nodes - cocoder39/coco39_LC GitHub Wiki

847. Shortest Path Visiting All Nodes

The comparison between option1 and option2 is interesting!. The pruning logic in option 2 can be used for optimization for some problem but not for this one since this is a connected graph.

Option1: adding all start nodes to queue

There are 2 ^ n states for each node where n is number of nodes. T = O(n * 2^n)

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        visited = set()
        queue = collections.deque()
        for i in range(n):
            bitMask = 1 << i
            visited.add((i, bitMask))
            queue.append((i, bitMask, 0))
        
        while queue:
            curNode, curState, curLen = queue.popleft()
            if curState == (1 << n) - 1:
                return curLen
            for neighbor in graph[curNode]:
                nextState = curState | (1 << neighbor)
                if (neighbor, nextState) not in visited:
                    visited.add((neighbor, nextState))
                    queue.append((neighbor, nextState, curLen+1))
        return -1

Option 2: running bfs for each start point

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        res = -1
        for i in range(len(graph)):
            length = self.bfs(graph, i)
            if length == -1:
                return -1
            if res == -1:
                res = length
            else:
                res = min(res, length)
        return res
    
    def bfs(self, graph, start):
        n = len(graph)
        bitMask = 1 << start
        if bitMask == (1 << n) - 1:
            return 0
        
        visited = set((start, bitMask))
        queue = collections.deque()
        queue.append((start, bitMask, 0))
        while queue:
            curNode, curState, curLen = queue.popleft()
            for neighbor in graph[curNode]:
                newState = curState | (1 << neighbor)
                if newState == (1 << n) - 1:
                    return curLen + 1
                if (neighbor, newState) not in visited:
                    visited.add((neighbor, newState))
                    queue.append((neighbor, newState, curLen+1))
        return -1
        

Option 3: dfs

dfs not a good solution for shortest path.

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        res = float("inf")
        for i in range(n):
            state = 1 << i
            res = min(res, self.dfs(graph, i, state, set(), 0))
        return res
    
    def dfs(self, graph, node, state, visited, length):
        n = len(graph)
        if state == (1 << n) - 1:
            return length
        
        res = float("inf")
        for neighbor in graph[node]:
            nextState = state | (1 << neighbor)
            if (neighbor, nextState) not in visited:
                visited.add((neighbor, nextState))
                res = min(res, self.dfs(graph, neighbor, nextState, visited, length+1))
                visited.remove((neighbor, nextState))
        return res