Shortest Path Visiting All Nodes - Leetcode Solution

The problem Shortest Path Visiting All Nodes on LeetCode asks us to find the shortest path that visits all nodes in a given graph exactly once. This is a classic problem in graph theory, and there are several algorithmic solutions to it.

Approach:

The most popular approach to find the shortest path visiting all nodes is by using the Breadth-First Search (BFS). In this approach, we start with an initial node and explore all its neighbors before moving on to other nodes. We maintain a distance array to keep track of the shortest distance between the current node and all other nodes. Also, we will maintain some state to ensure that we visit each node exactly once.

Algorithm:

1. Initialize a queue with the initial node and mark it as visited.

2. While the queue is not empty:

   1. Dequeue the node at the front of the queue and explore its neighbors.

   2. For each neighbor that has not been visited before, update its distance and mark it as visited. Add the neighbor to the queue.

   3. If all nodes have been visited, return the distance of the last visited node.

3. If there is no path that visits all nodes exactly once, return -1.

To ensure that we visit each node exactly once, we can maintain a state variable that represents the set of nodes visited so far.

Code:

public int shortestPathLength(int[][] graph) {
    int n = graph.length;
    int[][] state = new int[n][1 << n];
   
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        Arrays.fill(state[i], Integer.MAX_VALUE);
        state[i][1 << i] = 0;
        queue.offer(new int[] {i, 1 << i});
    }

    while (!queue.isEmpty()) {
        int[] nodeCurr = queue.poll();
        int node = nodeCurr[0];
        int mask = nodeCurr[1];
        
        if (mask == (1 << n) - 1) {
            return state[node][mask];
        }

        for (int neighbor : graph[node]) {
            int currMask = mask | (1 << neighbor);
            if (state[neighbor][currMask] > state[node][mask] + 1) {
                state[neighbor][currMask] = state[node][mask] + 1;
                queue.offer(new int[] {neighbor, currMask});
            }
        }
    }

    return -1;
}

In this code, we use BFS to iterate over the nodes and their neighbors. We use state to keep track of the nodes visited so far and their respective distances from the initial node. We maintain a queue to process the nodes in a breadth-first fashion.

The time complexity of this algorithm is O(n * 2^n), where n is the number of nodes in the graph.

1