847. Shortest Path Visiting All Nodes LeetCode Solution
In this guide, you will get 847. Shortest Path Visiting All Nodes LeetCode Solution with the best time and space complexity. The solution to Shortest Path Visiting All Nodes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Shortest Path Visiting All Nodes
You have an undirected, connected graph of n nodes labeled from 0 to n – 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.
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: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
Constraints:
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i] does not contain i.
If graph[a] contains b, then graph[b] contains a.
The input graph is always connected.
Complexity Analysis
Time Complexity: O(2^n \cdot n)
Space Complexity: O(2^n \cdot n)
847. Shortest Path Visiting All Nodes LeetCode Solution in C++
class Solution {
public:
int shortestPathLength(vector<vector<int>>& graph) {
const int n = graph.size();
const int goal = (1 << n) - 1;
queue<pair<int, int>> q; // (u, state)
vector<vector<bool>> seen(n, vector<bool>(1 << n));
for (int i = 0; i < n; ++i)
q.emplace(i, 1 << i);
for (int step = 0; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [u, state] = q.front();
q.pop();
if (state == goal)
return step;
if (seen[u][state])
continue;
seen[u][state] = true;
for (const int v : graph[u])
q.emplace(v, state | 1 << v);
}
return -1;
}
}; /* code provided by PROGIEZ */
847. Shortest Path Visiting All Nodes LeetCode Solution in Java
class Solution {
public int shortestPathLength(int[][] graph) {
final int n = graph.length;
final int goal = (1 << n) - 1;
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(); // (u, state)
boolean[][] seen = new boolean[n][1 << n];
for (int i = 0; i < n; ++i)
q.offer(new Pair<>(i, 1 << i));
for (int step = 0; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int u = q.peek().getKey();
final int state = q.poll().getValue();
if (state == goal)
return step;
if (seen[u][state])
continue;
seen[u][state] = true;
for (final int v : graph[u])
q.offer(new Pair<>(v, state | 1 << v));
}
return -1;
}
} // code provided by PROGIEZ
847. Shortest Path Visiting All Nodes LeetCode Solution in Python
class Solution:
def shortestPathLength(self, graph: list[list[int]]) -> int:
n = len(graph)
goal = (1 << n) - 1
q = collections.deque() # (u, state)
seen = set()
for i in range(n):
q.append((i, 1 << i))
step = 0
while q:
for _ in range(len(q)):
u, state = q.popleft()
if state == goal:
return step
if (u, state) in seen:
continue
seen.add((u, state))
for v in graph[u]:
q.append((v, state | 1 << v))
step += 1
return -1 # code by PROGIEZ
