Skip to main content

847. Shortest Path Visiting All Nodes

hard

Find the shortest path in an undirected graph that visits every node (Travelling Salesman on small n). BFS on the (current_node, visited_mask) state space.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • n == graph.length
  • 1 <= n <= 12
  • 0 <= graph[i].length < n
  • graph[i] does not contain i.
  • If graph[a] contains b, then graph[b] contains a.
  • The input graph is always connected.

Examples

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

n <= 12, so the set of visited nodes fits in a 12-bit mask: 4096 possible states.

Hint 2

State = (current_node, visited_mask). There are n * 2^n states ≤ 12 * 4096 = ~49k.

Hint 3

Run BFS from every starting state (i, 1 << i) simultaneously. The first time you pop a state with mask == (1 << n) - 1 you have the answer.

Solution approach

Reveal approach

Multi-source BFS over the (node, mask) state graph. Seed the BFS queue with every (i, 1 << i) for i in 0..n-1 — you may start from any node. Track visited states in a 2D boolean array of size n * 2^n. At each BFS step, dequeue (u, mask) with distance d. If mask == (1 << n) - 1, return d. Otherwise, for each neighbor v in graph[u], compute new_mask = mask | (1 << v). If (v, new_mask) hasn't been visited, mark it and enqueue with distance d + 1. Time and space are both O(n * 2^n * average_degree). The bitmask collapses the visited-set into an int so transition is O(1).

Complexity

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

Related patterns

  • bit-manipulation
  • bfs
  • dynamic-programming
  • bitmask-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More Bit Manipulation practice problems

See all Bit Manipulation problems →