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

题目描述

给了一个无向联通图，图中节点个数是n，编号从0-n-1，
问能访问所有节点的最短路径长度是多少？可以从任一节点开始和停止，可多次访问节点，可重用边。

f1-bfs+状态压缩

基本分析

1. 节点的个数不超过12，暗示什么？可能对节点的访问状态进行二进制压缩
2. 每条边长度是1，求最短路径可以联想到啥方法？bfs
3. 这里和常见的bfs不同点在哪？<1>不限制起点和终点？->对所有起点需要枚举；<2>需要记录节点的经过情况？->在遍历元素中追加每个节点的经过情况; <3>需要知道当前长度？->元素中追加路径长度
4. 怎么保证每个节点u和节点的经过情况mask只被搜索到一次？定义辅助数组vis，对入队的(u,mask）进行判断
5. bfs初始化时需要考虑什么？<1>n个起点放到q中；<2>n个起点对应的(u, 1<<u)放到vis中
6. while 的退出条件是什么？某次弹出的mask是(1<<n)-1, 表示所有的节点都访问到了
7. 从u到u的邻接点v，怎么更新mask？把mask对应的第v位的值更新为1，mask_v = mask | (1<<v)

代码

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        q = deque((u, 1<<u, 0) for u in range(n))
        vis = set()
        for i in range(n):
            vis.add((i, 1<<i))
        ans = 0

        while q:
            u, mask, d = q.popleft()
            if mask == (1<<n)-1:
                ans = d
                break
            for v in graph[u]:
                mask_v = mask | (1<<v)
                if not (v, mask_v) in vis:
                    q.append((v, mask_v, d+1))
                    vis.add((v, mask_v))
        
        return ans

复杂度

时间：常规的bfs复杂度是\(O(n+m)\),其中n为点数，m为边数，这里m没显示给出，最差为\(m=O(n^2)\)。由于引入了mask维度，总的复杂度是\(O(2^n*n^2)\)
空间：队列需要的空间时\(O(2^n*n)\)

总结

1. 看到边长都是1且求最短路径，那么可能会用bfs做
2. 由于没有约束起点，bfs的时候需要把所有点当做可能的起点入队
3. 由于还需要知道遍历情况和当前路径长，需要在u之外额外引入mask以及d参数
4. 需要考虑节点u和对应的经过情况（u，mask）只被搜索一次，需要引入辅助集合vis

f2-预处理点对最短路+动态规划+状态压缩

基本分析

1. 如果考虑用动态规划处理，需要先知道啥，怎么做？需要知道任意点对(i, j)的最短路，可以用n次bfs或者Floyd
2. 由于经过的路径可能不是最合理的，怎么在定义状态时，保证所枚举的点是有用的？引出关键节点的定义，枚举关键节点进行状态转移
3. dp状态怎么定义？f[u][mask]表示用任一节点到节点u开始，冰洁经过的关键节点对应的二进制表示为mask时的最短路径长度
4. 怎么进行状态转移？由于u是最后一个关键节点，可以枚举上一个关键节点v进行转移，f[u][mask] = min(f[u][mask], f[v][mask\u]+d[v][u])
5. 初始化dp时怎么考虑？在遍历状态的时候，如果当前mask只有一个1，表示就是起点，这个时候找到1的位置，就是u，定义f[u][mask]=0
6. 怎么拿到最后的结果？mask肯定需要是(1<<n)-1,但是最后的点u可能有不同，需要在u的维度上进行枚举取最小

代码

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

        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 = [[inf] *(1<<n) for _ in range(n)]

        for state in range(1, 1<<n):
            if (state & (state-1)) == 0:
                u = bin(state).count('0') - 1
                f[u][state] = 0
            else:
                for u in range(n):
                    if state & (1<<u):
                        for v in range(n):
                            if state & (1<<v) and u != v:
                                state_u = state ^ (1<<u)
                                f[u][state] = min(f[u][state], f[v][state_u]+d[v][u])
        
        ans = min(f[i][-1] for i in range(n))
        return ans

复杂度

时间：状态的总数是\(O(n*2^n)\),每个状态需要\(O(n)\)枚举，总计\(O(n^2*2^n)\)
空间：存储状态需要\(o(n*2^n)\)

总结

1. 怎么初始化以及计算点对的最短路径？<1>相邻点的距离初始化为1，其他情况初始化为一个大值n+1; <2>转移时用Floyd
2. 怎么定义dp的初值？维度是n*mask, 先赋大值inf。对于起点的初值，在遍历mask的时候同步看情况置为0
3. 遍历mask之后为啥要遍历u，u对mask有啥要求？根据状态定义，遍历u表示最后一个关键点是u，因为对同一个mask可能最后一个关键点不同，走法就不同。mask对应的u位置肯定需要是1，不是的话跳过u去找下一个
4. 在遍历v的时候，v需要是u的邻接点吗?对v的要求有啥？要怎么进行转移？这里是枚举关键节点，可能是走法的子序列，所以v不一定和u相邻，所以是在n范围内枚举v；mask对应的v的位置也需要是1，同时u!=v；新的dp值取min(f[u][mask]，f[v][mask\u]+d[v][u])