数据结构与算法 / 系统课时
最短路和状态压缩怎么结合
最短路和状态压缩怎么结合
当图上只有少量“必须访问、必须收集或只能触发一次”的特殊状态时,仅记录当前位置已经不够。把当前位置与位掩码合成搜索状态,就能在保持最短路框架的同时,准确表示已经完成了哪些条件。
学习目标
- 能把“节点位置 + 已完成条件”建模为联合状态
- 能根据边权选择 BFS 或 Dijkstra,并估算状态空间复杂度
- 能识别状态压缩最短路适合与不适合的问题规模
从普通最短路扩展状态
普通最短路常用 dist[u] 表示到节点 u 的最短距离,但如果题目要求“经过全部特殊点”,同一个节点在“已访问特殊点 A”和“尚未访问 A”时,后续可行性完全不同。
因此把状态改成 (u, mask):u 表示当前位置,mask 的第 i 位表示第 i 个特殊条件是否已经完成。转移到相邻节点 v 时,如果 v 对应某个特殊点,就把相应位设为 1。

这样做的关键不是“在最短路里额外塞一个整数”,而是把原图扩成了最多 n * 2^k 个状态,其中 k 是被压缩的特殊条件数。
什么时候用 BFS,什么时候用 Dijkstra
如果原图每条边代价都相同,联合状态图仍然是等权图,直接 BFS 即可。若边权不同但都非负,就把 (u, mask) 当作 Dijkstra 的节点,维护 dist[u][mask]。
状态压缩不会改变最短路算法成立的条件,只会扩大状态数量。等权图 BFS 的时间量级约为 O((n + m) * 2^k);非负加权图使用堆优化 Dijkstra 时,还会增加优先队列操作的对数开销。
用 BFS 找到经过全部特殊点的最短路
下面的完整示例在无权无向图中,从节点 0 出发到节点 5,并要求途中访问特殊点 2 和 4。队列中的每个元素同时携带当前位置、掩码和当前距离。
from collections import deque
def shortest_path_visit_all(n, edges, start, target, special_nodes):
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
# 每个特殊节点占用 mask 中的一位。
bit_index = {node: i for i, node in enumerate(special_nodes)}
full_mask = (1 << len(special_nodes)) - 1
start_mask = 0
if start in bit_index:
start_mask |= 1 << bit_index[start]
queue = deque([(start, start_mask, 0)])
# 同一节点配上不同 mask,必须视为不同搜索状态。
visited = {(start, start_mask)}
while queue:
u, mask, dist = queue.popleft()
if u == target and mask == full_mask:
return dist
for v in graph[u]:
next_mask = mask
if v in bit_index:
next_mask |= 1 << bit_index[v]
state = (v, next_mask)
if state not in visited:
visited.add(state)
queue.append((v, next_mask, dist + 1))
return -1
if __name__ == '__main__':
n = 6
edges = [
(0, 1), (1, 2), (2, 3),
(3, 5), (1, 4), (4, 5)
]
print(shortest_path_visit_all(n, edges, 0, 5, [2, 4]))预期输出
5最短距离为 5,例如可以走 0 -> 1 -> 2 -> 1 -> 4 -> 5。这里允许重复经过普通节点,因为“是否重复走过节点”不是状态条件;真正需要记录的是两个特殊点是否已经访问。
建模时最容易错的边界
第一类错误是只按节点去重。若写成 visited[u],算法会把“到达同一节点但完成条件不同”的状态错误合并,导致漏解。去重键必须同时包含节点和 mask。
第二类错误是把所有业务条件都塞进位掩码。只有取值很少、可离散,并且会影响未来决策的条件才值得进入状态;大范围计数或完整路径历史通常会让状态空间迅速失控。
如果特殊点数量很小、原图较大,而问题只关心这些关键点之间的移动,还可以先求关键点两两最短距离,再在更小的关键点图上做状态压缩 DP 或最短路。