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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int ShortestPathLength(int[][] graph) {
6 int n = graph.Length;
7 Queue<(int, int, int)> queue = new Queue<(int, int, int)>();
8 bool[,] seen = new bool[n, 1 << n];
9 for (int i = 0; i < n; i++) {
10 queue.Enqueue((i, 1 << i, 0));
11 seen[i, 1 << i] = true;
12 }
13 while (queue.Count > 0) {
14 var (node, visited, dist) = queue.Dequeue();
15 if (visited == (1 << n) - 1) {
16 return dist;
17 }
18 for (int j = 0; j < graph[node].Length; j++) {
19 int neighbor = graph[node][j];
20 int newVisited = visited | (1 << neighbor);
21 if (!seen[neighbor, newVisited]) {
22 queue.Enqueue((neighbor, newVisited, dist + 1));
23 seen[neighbor, newVisited] = true;
24 }
25 }
26 }
27 return -1;
28 }
29}Utilizing C#’s tuple functionality, this approach performs much like other BFS methods using bitmask states. Once all nodes are marked as visited within each possible path, the minimal distance path is returned.