数据结构与算法 / 系统课时

最短路和状态压缩怎么结合

最短路和状态压缩怎么结合

当图上只有少量“必须访问、必须收集或只能触发一次”的特殊状态时,仅记录当前位置已经不够。把当前位置与位掩码合成搜索状态,就能在保持最短路框架的同时,准确表示已经完成了哪些条件。

学习目标

  • 能把“节点位置 + 已完成条件”建模为联合状态
  • 能根据边权选择 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。队列中的每个元素同时携带当前位置、掩码和当前距离。

python
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]))

预期输出

text
5

最短距离为 5,例如可以走 0 -> 1 -> 2 -> 1 -> 4 -> 5。这里允许重复经过普通节点,因为“是否重复走过节点”不是状态条件;真正需要记录的是两个特殊点是否已经访问。

建模时最容易错的边界

第一类错误是只按节点去重。若写成 visited[u],算法会把“到达同一节点但完成条件不同”的状态错误合并,导致漏解。去重键必须同时包含节点和 mask。

第二类错误是把所有业务条件都塞进位掩码。只有取值很少、可离散,并且会影响未来决策的条件才值得进入状态;大范围计数或完整路径历史通常会让状态空间迅速失控。

如果特殊点数量很小、原图较大,而问题只关心这些关键点之间的移动,还可以先求关键点两两最短距离,再在更小的关键点图上做状态压缩 DP 或最短路。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最短路和状态压缩怎么结合

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通