Formatted question description: https://leetcode.ca/all/847.html

847. Shortest Path Visiting All Nodes

Level

Hard

Description

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. 1 <= graph.length <= 12
2. 0 <= graph[i].length < graph.length

Solution

Use breadth first search. Each state can be represented by the nodes covered and the current node. Use each node as a start node to create a state, and do breadth first search. If a state such that all nodes are covered is met, return the state’s corresponding distance.

• Java
• C++
• Python

• class Solution {
      public int shortestPathLength(int[][] graph) {
          int nodes = graph.length;
          int totalStates = 1 << nodes;
          Queue<int[]> queue = new LinkedList<int[]>();
          int[][] distances = new int[totalStates][nodes];
          for (int i = 0; i < totalStates; i++) {
              for (int j = 0; j < nodes; j++)
                  distances[i][j] = nodes * nodes;
          }
          for (int i = 0; i < nodes; i++) {
              queue.offer(new int[]{1 << i, i});
              distances[1 << i][i] = 0;
          }
          int minDistance = Integer.MAX_VALUE;
          while (!queue.isEmpty()) {
              int[] state = queue.poll();
              int distance = distances[state[0]][state[1]];
              if (state[0] == (1 << nodes) - 1) {
                  minDistance = distance;
                  break;
              }
              int[] children = graph[state[1]];
              for (int child : children) {
                  int nextNodes = state[0] | (1 << child);
                  if (distances[nextNodes][child] > distance + 1) {
                      distances[nextNodes][child] = distance + 1;
                      queue.offer(new int[]{nextNodes, child});
                  }
              }
          }
          return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
      }
  }
  

• // OJ: https://leetcode.com/problems/shortest-path-visiting-all-nodes/
  // Time: O(2^N * N)
  // Space: O(2^N * N)
  // Ref: https://leetcode.com/problems/shortest-path-visiting-all-nodes/discuss/135809/Fast-BFS-Solution-(46ms)-Clear-Detailed-Explanation-Included
  class Solution {
      int getKey(int i, int mask) {
          return (i << 12) + mask;
      }
  public:
      int shortestPathLength(vector<vector<int>>& G) {
          int N = G.size(), all = (1 << N) - 1, step = 0;
          queue<int> q;
          unordered_set<int> seen;
          for (int i = 0; i < N; ++i) {
              int k = getKey(i, 1 << i);
              q.push(k);
              seen.insert(k);
          }
          while (q.size()) {
              int cnt = q.size();
              while (cnt--) {
                  int k = q.front(), u = k >> 12, mask = k & ((1 << 12) - 1);
                  q.pop();
                  if (mask == all) return step;
                  for (int v : G[u]) {
                      int next = getKey(v, mask | (1 << v));
                      if (seen.count(next)) continue;
                      seen.insert(next);
                      q.push(next);
                  }
              }
              ++step;
          }
          return -1;
      }
  };
  

• class Solution(object):
      def shortestPathLength(self, graph):
          """
          :type graph: List[List[int]]
          :rtype: int
          """
          N = len(graph)
          que = collections.deque()
          step = 0
          goal = (1 << N) - 1
          visited = [[0 for j in range(1 << N)] for i in range(N)]
          for i in range(N):
              que.append((i, 1 << i))
          while que:
              s = len(que)
              for i in range(s):
                  node, state = que.popleft()
                  if state == goal:
                      return step
                  if visited[node][state]:
                      continue
                  visited[node][state] = 1
                  for nextNode in graph[node]:
                      que.append((nextNode, state | (1 << nextNode)))
              step += 1
          return step
  

All Problems

All Solutions