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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_N 12
6#define MAX_STATE (1<<MAX_N)
7
8int shortestPathLength(int** graph, int graphSize, int* graphColSize) {
9 int queue[MAX_N * MAX_STATE][3];
10 int front = 0, rear = 0;
11 bool seen[MAX_N][MAX_STATE] = {{false}};
12
13 for (int i = 0; i < graphSize; i++) {
14 queue[rear][0] = i;
15 queue[rear][1] = 1 << i;
16 queue[rear][2] = 0;
17 rear++;
18 seen[i][1 << i] = true;
19 }
20
21 while (front < rear) {
22 int *top = queue[front++];
23 int node = top[0], visited = top[1], dist = top[2];
24 if (visited == (1 << graphSize) - 1) {
25 return dist;
26 }
27 for (int j = 0; j < graphColSize[node]; j++) {
28 int neighbor = graph[node][j];
29 int newVisited = visited | (1 << neighbor);
30 if (!seen[neighbor][newVisited]) {
31 queue[rear][0] = neighbor;
32 queue[rear][1] = newVisited;
33 queue[rear][2] = dist + 1;
34 rear++;
35 seen[neighbor][newVisited] = true;
36 }
37 }
38 }
39 return -1;
40}In C, we manage a queue using a fixed-size array for simplicity's sake, although a dynamic queue would be more typical. The logic remains similar to other languages, relying heavily on bitmasking and BFS to manage state transitions efficiently.