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.
1from collections import deque
2
3def shortestPathLength(graph):
4 n = len(graph)
5 queue = deque()
6 seen = [[False] * (1 << n) for _ in range(n)]
7 for i in range(n):
8 queue.append((i, 1 << i, 0))
9 seen[i][1 << i] = True
10
11 while queue:
12 node, visited, dist = queue.popleft()
13 if visited == (1 << n) - 1:
14 return dist
15 for neighbor in graph[node]:
16 new_visited = visited | (1 << neighbor)
17 if not seen[neighbor][new_visited]:
18 seen[neighbor][new_visited] = True
19 queue.append((neighbor, new_visited, dist + 1))
20 return -1We use a queue to perform a BFS while keeping track of visited nodes using a bitmask. The queue stores tuples (node, visited, distance). Initialize the queue with all nodes and their respective visited state. For each node, check if all nodes are visited; if so, return the current distance as it represents the shortest path.