# 847. Shortest Path Visiting All Nodes 访问所有节点的最短路径

## # 题目描述：

An undirected, connected graph of N nodes (labeled `0, 1, 2, ..., N-1`) is given as `graph`.

`graph.length = N`, and `j != i` is in the list `graph[i]` exactly once, if and only if nodes `i` and `j` are connected.

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.

Example 1:

``````Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
``````

Example 2:

``````Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
``````

Note:

1. 1 <= graph.length <= 12
2. 0 <= graph[i].length < graph.length

## # 解题方法

### # 方法一：BFS

``````class Solution(object):
def shortestPathLength(self, graph):
"""
:type graph: List[List[int]]
:rtype: int
"""
N = len(graph)
que = collections.deque()
step = 0
goal = (1 << N) - 1
visited = [[0 for j in range(1 << N)] for i in range(N)]
for i in range(N):
que.append((i, 1 << i))
while que:
s = len(que)
for i in range(s):
node, state = que.popleft()
if state == goal:
return step
if visited[node][state]:
continue
visited[node][state] = 1
for nextNode in graph[node]:
que.append((nextNode, state | (1 << nextNode)))
step += 1
return step
``````