847.md

847 Shortest Path Visiting All Nodes

Description

link

---

Solution : BFS + memo

memo : (s, n)

• s : state of the visited nodes, use binary type to record it
• n : current node in traverse

---

Code

Complexity T : O(n * logn) M : O(n * logn)

class Solution:
    def shortestPathLength(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        memo = set()
        final_state = (1 << len(graph)) - 1
        
        state = [(1 << i, i) for i in range(len(graph))]
        step = 0
        while True:
            new_state = []
            for s, n in state:
                if s == final_state:
                    return step
                for v in graph[n]:
                    if (s | 1 << v, v) not in memo:
                        new_state.append((s | 1 << v, v))
                        memo.add((s | 1 << v, v))
            step += 1
            state = new_state