Welcome to Subscribe On Youtube
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 <= graph.length <= 120 <= 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.
-
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: def shortestPathLength(self, graph: List[List[int]]) -> int: n = len(graph) dst = -1 ^ (-1 << n) q = deque() vis = [[False] * (1 << n) for _ in range(n)] for i in range(n): q.append((i, 1 << i, 0)) vis[i][1 << i] = True while q: u, state, dis = q.popleft() for v in graph[u]: nxt = state | (1 << v) if nxt == dst: return dis + 1 if not vis[v][nxt]: q.append((v, nxt, dis + 1)) vis[v][nxt] = True return 0 ############ 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 -
type tuple struct { u int state int dis int } func shortestPathLength(graph [][]int) int { n := len(graph) dst := -1 ^ (-1 << n) q := make([]tuple, 0) vis := make([][]bool, n) for i := 0; i < n; i++ { vis[i] = make([]bool, 1<<n) q = append(q, tuple{i, 1 << i, 0}) vis[i][1<<i] = true } for len(q) > 0 { t := q[0] q = q[1:] cur, state, dis := t.u, t.state, t.dis for _, v := range graph[cur] { next := state | (1 << v) if next == dst { return dis + 1 } if !vis[v][next] { q = append(q, tuple{v, next, dis + 1}) vis[v][next] = true } } } return 0 } -
function shortestPathLength(graph: number[][]): number { const n = graph.length; const q: number[][] = []; const vis: boolean[][] = new Array(n) .fill(false) .map(() => new Array(1 << n).fill(false)); for (let i = 0; i < n; ++i) { q.push([i, 1 << i]); vis[i][1 << i] = true; } for (let ans = 0; ; ++ans) { for (let k = q.length; k; --k) { const [i, st] = q.shift()!; if (st === (1 << n) - 1) { return ans; } for (const j of graph[i]) { const nst = st | (1 << j); if (!vis[j][nst]) { vis[j][nst] = true; q.push([j, nst]); } } } } }