LC 847. 访问所有节点的最短路径
题目描述
这是 LeetCode 上的 847. 访问所有节点的最短路径 ，难度为 困难。
存在一个由 $n$ 个节点组成的无向连通图，图中的节点按从 $0$ 到 $n - 1$ 编号。
给你一个数组 graph 表示这个图。其中，$graph[i]$ 是一个列表，由所有与节点 $i$ 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
示例 1：
1
2
3
4
5输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]
示例 2：
1
2
3
4
5输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]
提示：
- $n == graph.length$
- $1 <= n <= 12$
- $0 <= graph[i].length < n$
graph[i]不包含 $i$- 如果
graph[a]包含b，那么graph[b]也包含a - 输入的图总是连通图
基本分析
为了方便，令点的数量为 $n$，边的数量为 $m$。
这是一个等权无向图，题目要我们求从「一个点都没访问过」到「所有点都被访问」的最短路径。
同时 $n$ 只有 $12$，容易想到使用「状态压缩」来代表「当前点的访问状态」：使用二进制表示长度为 $32$ 的 int 的低 $12$ 来代指点是否被访问过。
我们可以通过一个具体的样例，来感受下「状态压缩」是什么意思：
例如 $(000…0101)_2$ 代表编号为 $0$ 和编号为 $2$ 的节点已经被访问过，而编号为 $1$ 的节点尚未被访问。
然后再来看看使用「状态压缩」的话，一些基本的操作该如何进行：
假设变量 $state$ 存放了「当前点的访问状态」，当我们需要检查编号为 $x$ 的点是否被访问过时，可以使用位运算 a = (state >> x) & 1，来获取 $state$ 中第 $x$ 位的二进制表示，如果 a 为 $1$ 代表编号为 $x$ 的节点已被访问，如果为 $0$ 则未被访问。
同理，当我们需要将标记编号为 $x$ 的节点已经被访问的话，可以使用位运算 state | (1 << x) 来实现标记。
状态压缩 + BFS
因为是等权图，求从某个状态到另一状态的最短路，容易想到 BFS。
同时我们需要知道下一步能往哪些点进行移动，因此除了记录当前的点访问状态 $state$ 以外，还需要记录最后一步是在哪个点 $u$，因此我们需要使用二元组进行记录 $(state, u)$，同时使用 $dist$ 来记录到达 $(state, u)$ 使用的步长是多少。
一些细节：由于点的数量较少，使用「邻接表」或者「邻接矩阵」来存图都可以。对于本题，由于已经给出了 $graph$ 数组，因此可以直接充当「邻接表」来使用，而无须做额外的存图操作。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
int INF = 0x3f3f3f3f;
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int mask = 1 << n;
// 初始化所有的 (state, u) 距离为正无穷
int[][] dist = new int[mask][n];
for (int i = 0; i < mask; i++) Arrays.fill(dist[i], INF);
// 因为可以从任意起点出发，先将起始的起点状态入队，并设起点距离为 0
Deque<int[]> d = new ArrayDeque<>(); // state, u
for (int i = 0; i < n; i++) {
dist[1 << i][i] = 0;
d.addLast(new int[]{1 << i, i});
}
// BFS 过程，如果从点 u 能够到达点 i，则更新距离并进行入队
while (!d.isEmpty()) {
int[] poll = d.pollFirst();
int state = poll[0], u = poll[1], step = dist[state][u];
if (state == mask - 1) return step;
for (int i : graph[u]) {
if (dist[state | (1 << i)][i] == INF) {
dist[state | (1 << i)][i] = step + 1;
d.addLast(new int[]{state | (1 << i), i});
}
}
}
return -1; // never
}
}
- 时间复杂度：点（状态）数量为 $n \times 2^n$，边的数量为 $n^2 \times 2^n$，
BFS复杂度上界为点数加边数，整体复杂度为 $O(n^2 \times 2^n)$ - 空间复杂度：$O(n \times 2^n)$
Floyd + 状压 DP
其实在上述方法中，我们已经使用了与 DP 状态定义分析很像的思路了。甚至我们的元祖设计 $(state, u)$ 也很像状态定义的两个维度。
那么为什么我们不使用 $f[state][u]$ 为从「没有点被访问过」到「访问过的点状态为 $state$」，并最后一步落在点 $u$ 的状态定义，然后跑一遍 DP 来做呢？
是因为如果从「常规的 DP 转移思路」出发，状态之间不存在拓扑序（有环），这就导致了我们在计算某个 $f[state][u]$ 时，它所依赖的状态并不确保已经被计算/更新完成，所以我们无法使用常规的 DP 手段来求解。
这里说的常规 DP 手段是指：枚举所有与 $u$ 相连的节点 $v$，用 $f[state’][v]$ 来更新 $f[state][u]$ 的转移方式。
常规的 DP 转移方式状态间不存在拓扑序，我们需要换一个思路进行转移。
对于某个 $state$ 而言，我们可以枚举其最后一个点 $i$ 是哪一个，充当其达到 $state$ 的最后一步，然后再枚举下一个点 $j$ 是哪一个，充当移动的下一步（当然前提是满足 $state$ 的第 $i$ 位为 $1$，而第 $j$ 位为 $0$）。
求解任意两点最短路径，可以使用 Floyd 算法，复杂度为 $O(n^3)$。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49class Solution {
int INF = 0x3f3f3f3f;
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int mask = 1 << n;
// Floyd 求两点的最短路径
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
for (int i = 0; i < n; i++) {
for (int j : graph[i]) dist[i][j] = 1;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// DP 过程，如果从 i 能够到 j 的话，使用 i 到 j 的最短距离（步长）来转移
int[][] f = new int[mask][n];
// 起始时，让所有状态的最短距离（步长）为正无穷
for (int i = 0; i < mask; i++) Arrays.fill(f[i], INF);
// 由于可以将任意点作为起点出发，可以将这些起点的最短距离（步长）设置为 0
for (int i = 0; i < n; i++) f[1 << i][i] = 0;
// 枚举所有的 state
for (int state = 0; state < mask; state++) {
// 枚举 state 中已经被访问过的点
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) == 0) continue;
// 枚举 state 中尚未被访问过的点
for (int j = 0; j < n; j++) {
if (((state >> j) & 1) == 1) continue;
f[state | (1 << j)][j] = Math.min(f[state | (1 << j)][j], f[state][i] + dist[i][j]);
}
}
}
int ans = INF;
for (int i = 0; i < n; i++) ans = Math.min(ans, f[mask - 1][i]);
return ans;
}
}
- 时间复杂度：Floyd 复杂度为 $O(n^3)$；DP 共有 $n \times 2^n$ 个状态需要被转移，每次转移复杂度为 $O(n)$，总的复杂度为 $O(n^2 \times 2^n)$。整体复杂度为 $O(\max(n^3, n^2 \times 2^n))$
- 空间复杂度：$O(n \times 2^n)$
AStar 算法
显然，从 $state$ 到 $state’$ 的「理论最小修改成本」为两者二进制表示中不同位数的个数。
同时，当且仅当在 $state$ 中 $1$ 的位置与 $state’$ 中 $0$ 存在边，才有可能取到这个「理论最小修改成本」。
因此直接使用当前状态 $state$ 与最终目标状态 1 << n 两者二进制表示中不同位数的个数作为启发预估值是合适的。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39class Solution {
int INF = 0x3f3f3f3f;
int n;
int f(int state) {
int ans = 0;
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) == 0) ans++;
}
return ans;
}
public int shortestPathLength(int[][] g) {
n = g.length;
int mask = 1 << n;
int[][] dist = new int[mask][n];
for (int i = 0; i < mask; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]); // state, u, val
for (int i = 0; i < n; i++) {
dist[1 << i][i] = 0;
q.add(new int[]{1<< i, i, f(i << 1)});
}
while (!q.isEmpty()) {
int[] poll = q.poll();
int state = poll[0], u = poll[1], step = dist[state][u];
if (state == mask - 1) return step;
for (int i : g[u]) {
int nState = state | (1 << i);
if (dist[nState][i] > step + 1) {
dist[nState][i] = step + 1;
q.add(new int[]{nState, i, step + 1 + f(nState)});
}
}
}
return -1; // never
}
}
- 时间复杂度：启发式搜索不讨论时空复杂度
- 空间复杂度：启发式搜索不讨论时空复杂度
最后
这是我们「刷穿 LeetCode」系列文章的第 No.847 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
