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.
1var shortestPathLength = function(graph) {
2 const n = graph.length;
3 const queue = [];
4 const seen = Array.from({length: n}, () => Array(1 << n).fill(false));
5 for (let i = 0; i < n; i++) {
6 queue.push([i, 1 << i, 0]);
7 seen[i][1 << i] = true;
8 }
9 while (queue.length > 0) {
10 const [node, visited, dist] = queue.shift();
11 if (visited === (1 << n) - 1) {
12 return dist;
13 }
14 for (const neighbor of graph[node]) {
15 const newVisited = visited | (1 << neighbor);
16 if (!seen[neighbor][newVisited]) {
17 queue.push([neighbor, newVisited, dist + 1]);
18 seen[neighbor][newVisited] = true;
19 }
20 }
21 }
22};This JavaScript implementation also uses BFS and a bitmask for tracking visited nodes. The queue manages tuples of the current node, bitmask for visited nodes, and the path distance. The BFS operation continues until all nodes have been visited, signified by the bitmask being all 1s.