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