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$ 数组,因此可以直接充当「邻接表」来使用,而无须做额外的存图操作。

image.png

代码:

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
class 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)$。

image.png

代码:

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
49
class 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 两者二进制表示中不同位数的个数作为启发预估值是合适的。

image.png

代码:

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
class 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 原题链接和其他优选题解。