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

Categories:

题目描述
思路分析
1. 解法一：状态 BFS（推荐）
相似题目

题目描述

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

思路分析

解法一：状态 BFS（推荐）

核心思路：

状态为 (node, mask)，表示当前在 node，已访问集合为 mask。

以所有节点为起点做多源 BFS，首次到达全 1 mask 即为最短路径。

使用二维数组记录最短步数避免重复。

复杂度分析：

时间复杂度：O(n * 2^n)，其中 n 表示节点数。

空间复杂度：O(n * 2^n)。

import java.util.ArrayDeque;
import java.util.Queue;

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
}

相似题目

题目	难度	考察点
752. 打开转盘锁	中等	BFS
864. 获取所有钥匙的最短路径	困难	状态 BFS
815. 公交路线	困难	BFS
1293. 网格中的最短路径	困难	BFS
1129. 颜色交替的最短路径	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/48774099