Sponsored
Sponsored
This approach uses a combination of Dynamic Programming (DP) with a Bitmask to represent the set of nodes visited and Breadth First Search (BFS) to explore the graph.
Each state can be defined by a tuple (current_node, visited_nodes), where current_node is the current node, and visited_nodes is a bitmask representing which nodes have been visited.
The goal is to find the shortest path when visited_nodes has every node set (i.e., all nodes visited). We explore the states using BFS until we find the goal state.
Time Complexity is O(n * 2^n) due to the exploration of states (node and visited set), and Space Complexity is O(n*2^n) for visited states storage.
1import java.util.*;
2
3public class Solution {
4 public int shortestPathLength(int[][] graph) {
5 int n = graph.length;
6 Queue<int[]> queue = new LinkedList<>();
7 boolean[][] seen = new boolean[n][1 << n];
8 for (int i = 0; i < n; i++) {
9 queue.offer(new int[]{i, 1 << i, 0});
10 seen[i][1 << i] = true;
11 }
12 while (!queue.isEmpty()) {
13 int[] element = queue.poll();
14 int node = element[0], visited = element[1], dist = element[2];
15 if (visited == (1 << n) - 1) {
16 return dist;
17 }
18 for (int neighbor : graph[node]) {
19 int newVisited = visited | (1 << neighbor);
20 if (!seen[neighbor][newVisited]) {
21 queue.offer(new int[]{neighbor, newVisited, dist + 1});
22 seen[neighbor][newVisited] = true;
23 }
24 }
25 }
26 return -1;
27 }
28}Similar to the Python implementation, this Java method uses BFS with a queue while maintaining visited states via a bitmask. Each entry in the queue is an int array representing the current node, visited nodes as a bitmask, and the distance. The algorithm checks for all nodes visited and returns the shortest distance found.