[数据结构与算法]847. 访问所有节点的最短路径

847. 访问所有节点的最短路径

方法一：状态压缩 + 广度优先搜索

题目需要求出「访问所有节点的最短路径的长度」，并且图中每一条边的长度均为 1，可以考虑使用广度优先搜索的方法求出最短路径。

在常规的广度优先搜索中，会在队列中存储节点的编号。对于本题而言，最短路径的前提是「访问了所有节点」，因此除了记录节点的编号以外，还需要记录每一个节点的经过情况。因此，我们使用三元组 (u, mask, dist) 表示队列中的每一个元素，其中：

• u 表示当前位于的节点编号；
• mask 是一个长度为 n 的二进制数，表示每一个节点是否经过。如果 mask 的第 i 位是
  1，则表示节点 i 已经过，否则表示节点 i 未经过；
• dist 表示到当前节点为止经过的路径长度。

初始时，将所有的 (i, 2ⁱ, 0) 放入队列，表示可以从任一节点开始。在搜索的过程中，如果当前三元组中的 mask 包含 n 个 1（即 mask = 2ⁿ - 1），那么就可以返回dist 作为答案。

为了保证广度优先搜索时间复杂度的正确性，即同一个节点 u 以及节点的经过情况 mask 只被搜索到一次，可以使用数组或者哈希表记录 (u, mask) 是否已经被搜索过，防止无效的重复搜索。

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        q = deque((i, 1 << i, 0) for i in range(n))
        seen = {(i, 1 << i) for i in range(n)}
        ans = 0
        
        while q:
            u, mask, dist = q.popleft()
            if mask == (1 << n) - 1:
                ans = dist
                break
            # 搜索相邻的节点
            for v in graph[u]:
                # 将 mask 的第 v 位置为 1
                mask_v = mask | (1 << v)
                if (v, mask_v) not in seen:
                    q.append((v, mask_v, dist + 1))
                    seen.add((v, mask_v))
        
        return ans

方法二：预处理点对间最短路 + 状态压缩动态规划

由于题目中给定的图是连通图，那么可以计算出任意两个节点之间 u, v 间的最短距离，记为 d(u, v)。这样一来，就可以使用动态规划的方法计算出最短路径。

对于任意一条经过所有节点的路径，它的某一个子序列（可以不连续）一定是 0, 1, ?, n?1 的一个排列。我们称这个子序列上的节点为「关键节点」。在动态规划的过程中，我们也是通过枚举「关键节点」进行状态转移的。

我们用 f[u][mask] 表示从任一节点开始到节点 u 为止，并且经过的「关键节点」对应的二进制表示为 mask 时的最短路径长度。由于 u 是最后一个「关键节点」，那么在进行状态转移时，我们可以枚举上一个「关键节点」v，即：

其中 mask\u 表示将 mask 的第 u 位从 1 变为 0 后的二进制表示。也就是说，「关键节点」v 在 mask 中的对应位置必须为 1，将 f[v][mask\u] 加上从 v 走到 u 的最短路径长度为 d(v, u)，取最小值即为 f[u][mask]。

最终的答案即为：

当 mask 中只包含一个 1 时，我们无法枚举满足要求的上一个「关键节点」v。这里的处理方式与方法一中的类似：若 mask 中只包含一个 1，说明我们位于开始的节点，还未经过任何路径，因此状态转移方程直接写为：

f[u][mask] = 0

此外，在状态转移方程中，我们需要多次求出 d(v, u)，因此我们可以考虑在动态规划前将所有的 d(v, u) 预处理出来。这里有两种可以使用的方法，时间复杂度均为 O(n^3)：

我们可以使用 Floyd 算法求出所有点对之间的最短路径长度；

我们可以进行 n 次广度优先搜索，第 i 次从节点 i 出发，也可以得到所有点对之间的最短路径长度。

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        d = [[n + 1] * n for _ in range(n)]
        for i in range(n):
            for j in graph[i]:
                d[i][j] = 1
        
        # 使用 floyd 算法预处理出所有点对之间的最短路径长度
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])

        f = [[float("inf")] * (1 << n) for _ in range(n)]
        for mask in range(1, 1 << n):
            # 如果 mask 只包含一个 1，即 mask 是 2 的幂
            if (mask & (mask - 1)) == 0:
                u = bin(mask).count("0") - 1
                f[u][mask] = 0
            else:
                for u in range(n):
                    if mask & (1 << u):
                        for v in range(n):
                            if (mask & (1 << v)) and u != v:
                                f[u][mask] = min(f[u][mask], f[v][mask ^ (1 << u)] + d[v][u])

        ans = min(f[u][(1 << n) - 1] for u in range(n))
        return ans

1、旅行商问题的一般形式

旅行商问题（TSP）：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的哈密顿回路。

本题是一道类似旅行商问题，区别在于：可以重复访问某些节点，且在遍历完最后一个节点后不用回到出发点。

2、广度优先搜索的原理

广度优先搜索（BFS）算法是一种盲目搜索算法，目的是系统地检查图中所有节点，直到找到结果为止。由于广度优先搜索的扩展原则是先生成的节点先扩展，所以可以求得最短路径。一般而言，利用一个队列 queue 来存储当前已经生成的节点，每次弹出队头元素进行下一步扩展。
例子：在以下图中寻找值为 8 的节点

首先将起点放入队列，这是第一个生成的节点。

开始第一轮循环，本轮队列中仅 1 个元素。
弹出队头元素 1，扩展，生成了 2, 3 两个节点，均放入队列。
队列中 1 个元素扩展完成，本次循环结束。开始新一轮循环，本轮队列中有 2 个元素

弹出队头元素 2，扩展，生成了 4, 5 两个节点，放入队列。

弹出队头元素 3，扩展生成 6, 7，放入队列。
队列中 2 个元素扩展完成，本次循环结束。开始新一轮循环，本轮队列中有 4 个元素

弹出队头元素 4，扩展生成 8，找到了答案，当前处在第 3 轮循环，所以最短路径为 3。此时本轮仍有 3 个元素未被扩展，但因为已经找到了答案，所以直接退出搜索。

但是 BFS 算法扩展的前提是，每个节点可以以任意顺序扩展，也即一个节点与所有它可以扩展的节点距离都相同。对于本题而言，需要求最短路径，且任意两个节点之间距离均为 1，所以可以使用 BFS 算法。

特别地，根据上述例子，我们需要每次记录本轮循环队列中的节点数量，以便最终判定最短路径长度；另一方面，对于已生成的节点，需要标记，防止重复被生成。**一般而言，为了写代码时更加方便直观，在扩展过程中不判断是否找到了答案，而是每次弹出队头元素时进行判断。**所以一般的 BFS 代码框架如下：

# 1.初始化队列及标记数组，存入起点
# 1.初始化队列及标记数组，存入起点
from collections import deque

q = deque()

# graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
graph = [[1,2],[0,3,4],[0,5,6],[1,7],[1,7],[2,7,8],[2,8],[3,4,5],[5,6]]
target = 4
vis = [False for i in graph] # vector

q.extend(graph[0]) # 存入起点，标记
vis[0] = True

# 2.开始搜索
while q:
    cur = q.popleft() # 弹出队头元素
#         找到答案，退出搜索
    if cur == target: 
        print("hello")
        break

#         action(cur) # 有些题目需要对当前元素做处理

    for x in graph[cur]:
        if not vis[x]:
            q.append(x)
            vis[x] = True

当然，我们也可以将当前扩展的距离作为一个变量一起存入队列：

from collections import deque

q = deque()
# graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
graph = [[1,2],[0,3,4],[0,5,6],[1,7],[1,7],[2,7,8],[2,8],[3,4,5],[5,6]]
target = 7
vis = [False for i in graph] 

q.append((0,0))         
vis[0] = True

while q:
    cur, dist = q.popleft() 
    print(cur,dist)
    if cur == target: 
        print("distance = ", dist)
        break
    
#         action(cur) # 有些题目需要对当前元素做处理

    for x in graph[cur]:
        if not vis[x]:
            q.append((x, dist + 1))
            vis[x] = True

3、状态压缩

本题与一般的图论题目不同的是，需要遍历完图内全部节点，且可以重复访问某些节点。所以需要在搜索过程中，记录当前已经遍历了哪些节点。如果利用数组来存储每个节点的状态，在传参时较为不方便，效率不高。本题数据范围 n ≤12，说明可以利用状态压缩。

状态压缩也即用一个变量来表示当前状态，比较常用的方式是利用一个 n 位 k 进制数 mask 表示当前 n 个节点的所处的 k 个不同状态。对于本题而言，某个节点只需要记录是否遍历过，所以利用二进制即可。

一般而言，mask 从低到高第 i 位为 0 表示第 i 个节点还未被访问过，为 1 则相反。例如，假设有 3 个点，点 1 遍历过，点 2, 3 未遍历，则 mask = 001；若点 3 遍历过，点 1, 2 未遍历，则 mask = 100 。特别地，三个点均未遍历时，mask = 000 = 0，均遍历过时，mask = 111 = 2 ^k
?1
一些状态压缩的基本操作如下：

• 访问第 i 个点的状态：state=(1 << i) & mask
• 更改第 i 个点状态为 1：mask = mask | (1 << i)

4、基于状态压缩的广度优先搜索算法

根据之前的介绍，本题可以通过广度优先搜索算法对图中节点进行扩展，并利用状态压缩记录节点的遍历情况。具体实现细节如下：

• BFS 参数：当前节点编号 idx，当前搜索状态 mask，当前扩展距离 dist
• BFS 起点：题目不限制起点，所以最开始可以将每个点都存入队列，对应状态为仅该点遍历。例如图中有 2 个点时，分别将第一个点及其对应的 mask = 01，第二个点和其对应的 mask = 10 存入。
• BFS 终点：最终要求所有点均遍历，所以当 mask = 2ⁿ - 1 时搜索结束。
• BFS 标记：尽管本题可以重复访问某些节点，但是在同一状态下重复访问某一节点必然是无用功。所以在实现时，利用一个二维标记数组记录某一状态下，某一节点的拓展情况，防止被重复扩展。

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        # 1.初始化队列及标记数组，存入起点
        # 三个属性分别为 idx, mask, dist；存入起点，起始距离 0
        q = deque((i, 1 << i, 0) for i in range(n))
        # 节点编号及当前状态 
        vis = {(i, 1 << i) for i in range(n)} 
        
        # 开始搜索
        while q:
            u, mask, dist = q.popleft() # 弹出队头元素
            if mask == (1 << n) - 1: # 找到答案，返回结果
                return dist
            # 扩展
            for x in graph[u]:
                nextmask = mask | (1 << x)
                if (x, nextmask) not in vis:
                    q.append((x, nextmask, dist + 1))
                    vis.add((x, nextmask))
        
        return 0