Tap here to switch tabs
Problem
Submissions

Problem: Shortest Path Visiting All Nodes

Shortest Path Visiting All Nodes gives an undirected connected graph and asks for the minimum number of edges in a walk that visits every node, with any start, end, and repeated visits allowed.

Statement

You are given an undirected connected graph with n nodes numbered from 00 to n−1n-1. The graph is provided as an adjacency list, graph, where graph[i] contains all nodes that share an edge with node i.

Your task is to find the length of the shortest path that visits every node. You may:

  • Start from any node.

  • End at any node.

  • Revisit nodes and reuse edges as many times as needed.

Constraints:

  • n ==== graph.length

  • 1≤1 \leq n ≤12\leq 12

  • 0≤0 \leq 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.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Shortest Path Visiting All Nodes

Shortest Path Visiting All Nodes gives an undirected connected graph and asks for the minimum number of edges in a walk that visits every node, with any start, end, and repeated visits allowed.

Statement

You are given an undirected connected graph with n nodes numbered from 00 to n−1n-1. The graph is provided as an adjacency list, graph, where graph[i] contains all nodes that share an edge with node i.

Your task is to find the length of the shortest path that visits every node. You may:

  • Start from any node.

  • End at any node.

  • Revisit nodes and reuse edges as many times as needed.

Constraints:

  • n ==== graph.length

  • 1≤1 \leq n ≤12\leq 12

  • 0≤0 \leq 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.