Solution: Shortest Path Visiting All Nodes
Explore how to apply breadth-first search combined with bitmask state compression to determine the shortest path that visits every node in an undirected connected graph. Understand how to represent states with current nodes and visited sets, and avoid redundant searches to find the minimal number of steps efficiently.
We'll cover the following...
We'll cover the following...
Statement
You are given an undirected connected graph with n nodes numbered from 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:
ngraph.lengthn...