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

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[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;
}
}