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.
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6int shortestPathLength(vector<vector<int>>& graph) {
7 int n = graph.size();
8 queue<tuple<int, int, int>> q;
9 vector<vector<bool>> seen(n, vector<bool>(1 << n, false));
10 for (int i = 0; i < n; i++) {
11 q.emplace(i, 1 << i, 0);
12 seen[i][1 << i] = true;
13 }
14
15 while (!q.empty()) {
16 auto [node, visited, dist] = q.front();
17 q.pop();
18 if (visited == (1 << n) - 1) {
19 return dist;
20 }
21 for (int neighbor : graph[node]) {
22 int newVisited = visited | (1 << neighbor);
23 if (!seen[neighbor][newVisited]) {
24 seen[neighbor][newVisited] = true;
25 q.emplace(neighbor, newVisited, dist + 1);
26 }
27 }
28 }
29 return -1;
30}This C++ uses a tuple to manage node state in the queue. It still relies on BFS with a bitmask to efficiently explore all states in the graph, tracking distances for the shortest path covering all nodes.