Q847. Shortest Path Visiting All Nodes

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

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.

 

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
 

Note:

1 <= graph.length <= 12
0 <= graph[i].length < graph.length

I did not get this question and it did look very complicated to me. Before going to the solution, I should say that there are some general ideas to wear before thinking about a question involving shortest path.

• Shortest path from a start to an end (Dijkstra’s).
• Shortest path among all pairs of nodes (Floyd–Warshall).

For an unweighted graph, the Dijkstra’s algorithm is very similar to a BFS traverse.

For this question, the essential idea is to construct the state properly.

First of all, what could be a brute force approach? We explore the nodes randomly and we are free to go back and forth. But the problem is that we may get stuck by loop. So, we need to realize that we are in a loop. The trick to realize it is by constructing the state properly. Let’s say the state is the current explored notes and the current position. The edges that connect the state space are defined implicitly by the edges of the graph. In other word, at the current state, we can move to another state by exploring the neighbors of the current node (at the position).

OK, the initial state would be (explored node set = (node i), node i) and we can do BFS until hitting the state with explored node set = all nodes.

In terms of the data structure, we can use a series of binary numbers to represent if the nth node has been explored (the way to generate n bits with leading one is 1 << n).

And we would like to consider five initial state together and whenever we hit the target state we can return since the path length increases monotonically.

With these ideas, we have the Python submission:

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        if len(graph) == 0 or len(graph[0]) == 0:
            return 0
        # initialization
        queue = deque([ [1 << i, i] for i in range(len(graph)) ])
        mem_dict = { (1 << i, i): 0 for i in range(len(graph)) }
        while len(queue) > 0:
            cover, node = queue.popleft()
            for neigh in graph[node]:
                new_cover = cover | (1 << neigh)
                if new_cover == 2 ** len(graph) - 1:
                    return mem_dict[(cover, node)] + 1
                if (new_cover, neigh) not in mem_dict:
                    mem_dict[(new_cover, neigh)] = mem_dict[(cover, node)] + 1
                    queue.append((new_cover, neigh))