## 题目描述：

LeetCode 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`

## 解题思路：

Floyd + 动态规划（Dynamic Programming）

```利用Floyd求出每对顶点i, j之间的最短距离，记为dp[i][j]，代价为O(N^3)

status[ns][j] = min(status[ns][j], status[s][i] + dp[i][j])

## Python代码：

``````class Solution(object):
def shortestPathLength(self, graph):
"""
:type graph: List[List[int]]
:rtype: int
"""
INF = 0x7FFFFFFF
N = len(graph)
dp = [[INF] * N for x in range(N)]
for i, e in enumerate(graph):
dp[i][i] = 0
for j in e:
dp[i][j] = dp[j][i] = 1
for z in range(N):
for x in range(N):
for y in range(N):
dp[x][y] = min(dp[x][y], dp[x][z] + dp[z][y])

status = {(0, i) : 0 for i in range(N)}
for s in range(1 << N):
for i in range(N):
if (s, i) not in status: continue
v = status[(s, i)]
for j in range(N):
ns = s | (1 << j)
if status.get((ns, j), INF) > v + dp[i][j]:
status[(ns, j)] = v + dp[i][j]
return min(status[((1 << N) - 1, i)] for i in range(N))
``````

## Python代码：

``````class Solution(object):
def shortestPathLength(self, graph):
"""
:type graph: List[List[int]]
:rtype: int
"""
INF = 0x7FFFFFFF
N = len(graph)
dp = [[INF] * N for x in range(N)]
for i, e in enumerate(graph):
dp[i][i] = 0
for j in e:
dp[i][j] = dp[j][i] = 1
for z in range(N):
for x in range(N):
for y in range(N):
dp[x][y] = min(dp[x][y], dp[x][z] + dp[z][y])

self.best = INF
visits = set()
def dfs(s, c, t):
if t >= self.best: return
if c == N:
self.best = min(self.best, t)
return
for n in range(N):
if n in visits: continue
dfs(n, c + 1, t + dp[s][n])
visits.remove(n)

for n in range(len(graph)):
dfs(n, 1, 0)
visits.remove(n)
return self.best
``````

Pingbacks已关闭。