What is the shortest path visiting all nodes problem?

The problem involves finding the shortest path that visits every node in a graph using dynamic programming and bit manipulation techniques.

How can I optimize the solution for shortest path visiting all nodes?

Optimizing the solution involves using BFS with bitmasking for state representation and dynamic programming to avoid redundant calculations.

What is bitmasking in the context of this problem?

Bitmasking is used to efficiently represent which nodes have been visited during graph traversal, reducing memory usage and improving performance.

Why is dynamic programming useful for this problem?

Dynamic programming allows us to store intermediate results for each state, ensuring that we do not repeat calculations and helping us find the shortest path.

How does GhostInterview help with solving this problem?

GhostInterview breaks down the problem into manageable steps, guiding you through graph traversal, dynamic programming, and optimization techniques.

#847

Hard

auto_awesome动态·规划

LeetCode 题解工作台

访问所有节点的最短路径

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。给你一个数组 graph 表示这个图。其中， graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边…

动态规划位运算广度优先搜索图位掩码

题目描述

存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。

给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

示例 1：

输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]

示例 2：

输入：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
输入的图总是连通图

lightbulb

解题思路

方法一：状态压缩 + BFS

我们注意到 $n$ 的范围不超过 $12$ ，因此，我们可以用一个 $12$ 位的二进制数来表示每个节点的访问情况，其中第 $i$ 位为 $1$ 表示第 $i$ 个节点已经被访问过，为 $0$ 表示该节点还没有被访问过。

我们初始化队列 $q$ ，其中每个元素是一个二元素 $(i, st)$ ，表示当前位于节点 $i$ ，且已经遍历过的节点的集合为 $st$ 。初始时，队列中只有 $n$ 个元素，即 $(i, 2^i)$ ，表示可以从任一节点出发开始遍历。另外，我们用一个哈希表或数组 $vis$ 记录每个状态是否已经被搜索过，防止无效的重复搜索。

在 BFS 的过程中，我们每次取出队首元素 $(i, st)$ ，如果当前 $st$ 包含 $n$ 个 $1$ ，那么我们就找到了一条从起点出发的遍历路径，返回当前的步数即可。否则我们枚举当前节点 $i$ 的所有连边 $(i, j)$ ，如果 $(j, st \lor 2^j)$ 没有被搜索过，那么就将 $(j, st \lor 2^j)$ 加入队列 $q$ 中，并且用 $vis$ 记录它已经被搜索过。循环此过程，直到找到一条路径。

时间复杂度 $(n^2 \times 2^n)$ ，空间复杂度 $O(n \times 2^n)$ 。其中 $n$ 是图中的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        q = deque()
        vis = set()
        for i in range(n):
            q.append((i, 1 << i))
            vis.add((i, 1 << i))
        ans = 0
        while 1:
            for _ in range(len(q)):
                i, st = q.popleft()
                if st == (1 << n) - 1:
                    return ans
                for j in graph[i]:
                    nst = st | 1 << j
                    if (j, nst) not in vis:
                        vis.add((j, nst))
                        q.append((j, nst))
            ans += 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates proficiency in dynamic programming and graph traversal.
question_mark
The candidate understands bitmasking and its application in state representation.
question_mark
The candidate can efficiently analyze and optimize graph traversal problems using BFS.

warning

常见陷阱

外企场景

error
Not considering bitmasking as an efficient way to track visited nodes.
error
Failing to optimize the BFS to avoid redundant calculations.
error
Overlooking space complexity when representing all possible states.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Graph is directed, not undirected.
arrow_right_alt
Graph contains cycles or multiple connected components.
arrow_right_alt
You can only visit nodes in a specific order.

help

常见问题

外企场景

继续练习

#805 数组的均值分割 #787 K 站中转内最便宜的航班 #943 最短超级串