Hard

Shortest Path Visiting All Nodes

LAB

Given an undirected graph adjacency list, return the shortest path length that visits every node at least once.

EXAMPLES

Example 1

Input
{
  "graph": [
    [
      1,
      2,
      3
    ],
    [
      0
    ],
    [
      0
    ],
    [
      0
    ]
  ]
}

Output
4

FUNCTION SHAPE

graph: intMatrix→int

SOLUTION NOTE

The BFS state is (current node, visited-node bitmask). Once the bitmask contains every node, the current BFS level is the shortest path length.

Reveal reference solution +

pythonREFERENCE

def shortestPathLength(self, graph):
    n = len(graph)
    target = (1 << n) - 1
    q = deque((node, 1 << node) for node in range(n))
    seen = set(q)
    steps = 0

    while q:
        for _ in range(len(q)):
            node, mask = q.popleft()
            if mask == target:
                return steps
            for nei in graph[node]:
                state = (nei, mask | (1 << nei))
                if state not in seen:
                    seen.add(state)
                    q.append(state)
        steps += 1
    return -1

TimeO(2^n * n^2)

SpaceO(2^n * n)

Open on LeetCode ↗