You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.
Example 1:
Input: graph = [[1,2,3],[0],[0],[0]] Output: 4 Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] Output: 4 Explanation: One possible path is [0,1,4,2,3]
Constraints:
n == graph.length1 <= n <= 120 <= graph[i].length < ngraph[i] does not contain i.graph[a] contains b, then graph[b] contains a.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.
We 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.
Java
JavaScript
C
C++
C#
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.
Shortest Path Visiting All Nodes | Leetcode 847 | Live coding session 🔥🔥 | BFS + Bit Manipulation • Coding Decoded • 21,272 views views
Watch 9 more video solutions →Practice Shortest Path Visiting All Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor