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

约 6 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 腾讯 猿辅导
标签
动态规划 广度优先搜索 位运算 图 位掩码

题目描述

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

image-20260928225153737

image-20260928225153739

题意分析

在无向连通图中寻找一条访问全部节点的最短行走路线，长度按经过的边数计算。起点和终点可以任选，节点、边都允许重复经过。题目最多有 12 个节点，可以用一个整数的二进制位记录已经访问过哪些节点。

解法：状态 BFS

核心思路

[!blue]

只知道当前位置还不够：到达同一节点时，已经访问的节点集合不同，剩余任务也不同。因此状态定义为 (node, mask)，mask 的第 i 位为 1 表示节点 i 已访问；dist[node][mask] 记录到达这个状态的最少边数，-1 表示尚未发现。

从 node 沿边走到邻居 nei 后，新状态为 (nei, mask | (1 << nei))，距离增加 1。即使 nei 已经出现在集合里，也允许走过去，因为可能需要借它通往尚未访问的节点。判重必须针对整个二元状态；若同一状态再次出现，当前位置和剩余任务都相同，更长的历史路线没有保留价值。

每条转移都只经过一条边，可以在这个状态图上做 BFS。起点任选，所以同时将所有 (i, 1 << i) 以距离 0 入队；这等价于一起搜索所有起点，避免先固定某个起点而错过更短路线。

全部节点已访问时，掩码为 (1 << n) - 1。BFS 按距离从小到大处理状态，第一次取出这个掩码对应的状态，其距离就是所有起终点选择中的最优值。入队时立即填写距离，保证每个状态只进入队列一次。

解题步骤

  1. 将距离表初始化为 -1，计算全集掩码 full。
  2. 每个节点各自作为起点，初始掩码只包含自身，距离设为 0 并入队。
  3. 取出状态后先检查 mask == full，满足则返回当前距离。只有一个节点时，初始状态就满足条件，答案为 0。
  4. 遍历当前节点的邻居，更新访问集合；若新状态未发现，就记录距离加 1 并入队。题目保证图连通，因此一定能找到覆盖全部节点的路线。

代码实现

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int full = (1 << n) - 1;
        int[][] dist = new int[n][1 << n];
        Queue<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                dist[i][mask] = -1;
            }
        }

        for (int i = 0; i < n; i++) {
            // 每个节点都可作为零步起点，掩码先包含自身
            int mask = 1 << i;

            dist[i][mask] = 0;
            queue.offer(new int[] {
                i,
                mask
            });
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int node = cur[0];
            int mask = cur[1];

            if (mask == full) {
                return dist[node][mask];
            }

            for (int nei : graph[node]) {
                // 允许重访物理节点，但节点与访问集合共同判重
                int nextMask = mask | (1 << nei);

                if (dist[nei][nextMask] == -1) {
                    dist[nei][nextMask] = dist[node][mask] + 1;
                    queue.offer(new int[] {
                        nei,
                        nextMask
                    });
                }
            }
        }

        return -1;
    }
}

func shortestPathLength(graph [][]int) int {
    n := len(graph)
    full := (1 << n) - 1

    dist := make([][]int, n)
    for i := 0; i < n; i++ {
        dist[i] = make([]int, 1<<n)
        for j := 0; j < (1 << n); j++ {
            dist[i][j] = -1
        }
    }

    queue := make([][2]int, 0)
    for i := 0; i < n; i++ {
        // 每个节点都可作为零步起点，掩码先包含自身
        mask := 1 << i
        dist[i][mask] = 0
        queue = append(queue, [2]int{
            i,
            mask,
        })
    }

    for head := 0; head < len(queue); head++ {
        node := queue[head][0]
        mask := queue[head][1]
        if mask == full {
            return dist[node][mask]
        }

        for _, nei := range graph[node] {
            // 允许重访物理节点，但节点与访问集合共同判重
            nextMask := mask | (1 << nei)
            if dist[nei][nextMask] == -1 {
                dist[nei][nextMask] = dist[node][mask] + 1
                queue = append(queue, [2]int{
                    nei,
                    nextMask,
                })
            }
        }
    }

    return -1
}

复杂度分析

  • 时间复杂度：$O((n+E)2^n)$，其中 $E$ 为原图边数。初始化 $n2^n$ 个距离项，每种访问集合下至多扫描全部邻接边。
  • 空间复杂度：$O(n2^n)$，距离表与队列最多保存这一数量级的状态。

关键点总结

[!green]

  • 同一节点带不同掩码是不同状态，不能一概去重。
  • 起点任选通过多源同层初始化表达。

易错点总结

[!yellow]

  • 只从零出发可能错过更优起点。
  • 初始掩码为零，会漏记已站上的节点。
  • 全集写成二的 n 次方，而不是减一，永远无法由合法节点位组成。

相似题目

题目 难度 关联与区别
864. 获取所有钥匙的最短路径 困难 同样把当前位置与已完成集合组成状态，原题记录钥匙集合，本题记录已访问节点集合。
943. 最短超级串 困难 同样全覆盖并保留最后位置，原题利用字符串重叠定义转移代价，本题图上每步代价为1。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/48774099
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！