DevExCode

LeetCode 847: Shortest Path Visiting All Nodes Solution

Master LeetCode problem 847 (Shortest Path Visiting All Nodes), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use a breadth-first search (BFS) algorithm along with bit manipulation to keep track of visited nodes. We will maintain a state for each visited node and use a bitmask to represent the visited nodes. We will start the BFS from all possible starting nodes and track the shortest path that visits every node.

  1. Initialize a queue for BFS, a set to store visited states, and a distance counter.
  2. For each node as a starting point, add the initial state (node, bitmask of visited nodes) to the queue.
  3. Perform BFS by exploring neighbors of the current state. Update the visited set and enqueue the new state if not visited.
  4. Keep track of the minimum distance that visits all nodes.
  5. Repeat the process for all possible starting nodes.
  6. Return the minimum distance found.

Time Complexity: O(2^n * n^2), where n is the number of nodes. Space Complexity: O(2^n * n).

:

Solution Code

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            queue.offer(new int[] {i, 1 << i, 0});
            visited.add(i + " " + (1 << i));
        }
        
        int target = (1 << n) - 1;
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int node = curr[0];
            int state = curr[1];
            int steps = curr[2];
            
            if (state == target) {
                return steps;
            }
            
            for (int neighbor : graph[node]) {
                int nextState = state | (1 << neighbor);
                if (!visited.contains(neighbor + " " + nextState)) {
                    queue.offer(new int[] {neighbor, nextState, steps + 1});
                    visited.add(neighbor + " " + nextState);
                }
            }
        }
        
        return -1;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 847 (Shortest Path Visiting All Nodes)?

This page provides optimized solutions for LeetCode problem 847 (Shortest Path Visiting All Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 847 (Shortest Path Visiting All Nodes)?

The time complexity for LeetCode 847 (Shortest Path Visiting All Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 847 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 847 in Java, C++, or Python.

Back to LeetCode Solutions