We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Path Visiting All Nodes

Difficulty: Hard

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.

Key Insights

  • The problem can be approached using a bitmask to represent the states of visited nodes.
  • Dynamic programming can be used to store the minimum path lengths for different combinations of visited nodes.
  • A breadth-first search (BFS) or depth-first search (DFS) can be applied to explore the graph.
  • The maximum number of nodes (n) is limited to 12, allowing for a feasible solution using bitmasking.

Space and Time Complexity

Time Complexity: O(n^2 * 2^n)
Space Complexity: O(n * 2^n)

Solution

The solution involves using dynamic programming with bitmasking. We represent the visited state of nodes using a bitmask where each bit indicates whether a node has been visited. We maintain a DP table where dp[mask][i] represents the shortest path to visit the set of nodes represented by mask and ending at node i. The main steps include:

  1. Initialize the DP table for single-node visits.
  2. Iterate through all possible masks and nodes, updating the DP table based on previously calculated paths.
  3. Finally, compute the minimum path length that visits all nodes.

Code Solutions

from collections import deque

def shortestPathLength(graph):
    n = len(graph)
    all_visited = (1 << n) - 1
    dp = [[float('inf')] * n for _ in range(1 << n)]
    queue = deque()

    for i in range(n):
        dp[1 << i][i] = 0
        queue.append((1 << i, i))

    while queue:
        mask, u = queue.popleft()
        for v in graph[u]:
            new_mask = mask | (1 << v)
            if dp[new_mask][v] > dp[mask][u] + 1:
                dp[new_mask][v] = dp[mask][u] + 1
                queue.append((new_mask, v))

    return min(dp[all_visited][i] for i in range(n))
← Back to All Questions