Problem: Shortest Path Visiting All Nodes

hard

40 min

Understand how to find the shortest path that visits every node in an undirected connected graph. Explore using adjacency lists and graph algorithms, including revisiting nodes and reusing edges, to solve this problem efficiently.

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

hard

40 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