Shortest Path Visiting All Nodes
Problem Description
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: 4Explanation: One possible path is [0,1,4,2,3]
Constraints:
n == graph.length1 <= n <= 120 <= graph[i].length < ngraph[i]does not containi.- If
graph[a]containsb, thengraph[b]containsa. - The input graph is always connected.
Solve it on LeetCode
Approaches
1. BFS Traversal
Intuition:
The problem can be translated into finding the shortest path covering all nodes in a graph, known as the Traveling Salesman Problem (TSP). A breadth-first search (BFS) approach is useful here since it explores all nodes layer by layer, ensuring that the shortest path is found efficiently. By keeping track of the visited nodes using a bitmask for each queue state, we can efficiently manage what nodes have been visited so far.
Algorithm:
- Use a queue to perform BFS where each state contains the node index and the bitmask of visited nodes.
- Start from each node by pushing all nodes into the queue as starting points.
- For each state, explore all its neighbors and update the visited nodes' bitmask accordingly.
- If all nodes are visited (bitmask becomes
111...1), return the current path length as the result. - Use a set to keep track of visited states to prevent revisiting the same state, optimizing duplication handling.
Code:
- Time Complexity: O(2^n * n^2)) - There are (2^n) possible states for each node, and up to (n^2) transitions between nodes.
- Space Complexity: O(2^n * n)) - Space for the
visitedstate-array, helping to keep track of node states.
2. Dynamic Programming with Bitmasking
Intuition:
This approach uses dynamic programming (DP) in combination with bitmasking to systematically compute the minimum path step required to visit all nodes starting from any node. The bitmask represents the set of visited nodes, providing a compact way to represent subsets of nodes.
Algorithm:
- Define
dp[mask][i]as the shortest path that visits the set of nodes represented bymaskending at nodei. - For each node, initialize
dp[1 << i][i] = 0since it costs 0 steps to reach nodeiwhen starting ati. - Update the
dptable by considering transitions between nodes, updating the states for visited nodes' masks. - The final answer is the minimum value of
dp[(1 << n) - 1][i]for alli, as it represents visiting all nodes (mask111...1).
Code:
- Time Complexity: O(2^n * n^2)) - Each state
(mask, i)is updated through (n^2) possibilities. - Space Complexity: O(2^n * n)) - Space used by the DP table.