##### Welcome to Subscribe On Youtube

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

# 847. Shortest Path Visiting All Nodes

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],,,]

Output: 4

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

Example 2:

Input: [,[0,2,4],[1,3,4],,[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.

• class Solution {
public int shortestPathLength(int[][] graph) {
int nodes = graph.length;
int totalStates = 1 << nodes;
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][state];
if (state == (1 << nodes) - 1) {
minDistance = distance;
break;
}
int[] children = graph[state];
for (int child : children) {
int nextNodes = state | (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
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]);
}
}
}
}
}