Problem: Shortest Path Visiting All Nodes

Medium

30 min

Explore how to find the shortest path that visits all nodes in an undirected, connected graph. This lesson guides you through understanding problem constraints and implementing an efficient solution using adjacency lists and graph traversal techniques.

Statement

You are given an undirected connected graph with n nodes numbered from $0$ to $n-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 \leq$ n $\leq 12$
$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.

Shortest Path Visiting All Nodes

What is the shortest path length that visits all nodes of the following graph?

graph = $[[1,2], [0,3], [0,3], [1,2]]$

0 -- 1
|    |
2 -- 3

$4$

$3$

$2$

$1$

1 / 4

Problem: Shortest Path Visiting All Nodes

Medium

30 min

Statement

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 \leq$ n $\leq 12$
$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.

Shortest Path Visiting All Nodes

What is the shortest path length that visits all nodes of the following graph?

graph = $[[1,2], [0,3], [0,3], [1,2]]$

0 -- 1
|    |
2 -- 3

$4$

$3$

$2$

$1$

1 / 4

Problem: Shortest Path Visiting All Nodes

Statement

Examples

Understand the problem

Figure it out!

Try it yourself

Problem: Shortest Path Visiting All Nodes

Statement

Examples

Understand the problem

Figure it out!

Try it yourself