图搜索与路径恢复

图搜索题真正难的地方，往往不是把算法名背出来，而是先搞清楚“点是什么、边是什么、代价是什么、状态要不要扩展”，再决定该用 BFS 还是 Dijkstra。很多同学把最短路题做错，不是因为不会循环，而是因为只记了最小值，没有把完整路径一起恢复出来。

学习目标

• 学会把网格、道路、站点、通道等题面元素转成图结构。
• 学会区分无权图最短步数、带权图最小代价和双关键字最优路。
• 学会用 parent / prev 数组恢复完整路径。
• 学会处理不可达、并列路径和额外状态条件。

先判断题目属于哪一类图搜索

无权图或网格最短步数

如果每走一步代价都相同，只要求“最少步数”或“最少经过多少格”，优先考虑 BFS。

题库对应：

• 民族展馆导览：最短参观路径搜索

带权图最短路

如果边权不同，目标是总时间、总代价、总风险最小，优先考虑 Dijkstra。

题库对应：

• 红色路线与资源调度：长征片段补给路线规划

双关键字或状态扩展最短路

如果不是只比一个值，而是先比 A 再比 B，或者“位置 + 是否满足条件”共同决定状态，就要做状态扩展或双关键字比较。

题库对应：

• 丝路驿站传信：最少换站次数与最短耗时路径

第一步：建模

做图题前，先把下面四件事写清楚：

1. 节点是什么。
2. 边是什么。
3. 一次转移的代价是什么。
4. 最优目标是什么。

例如 s4-jh-07 中：

• 节点是网格里的可走位置。
• 边是四个方向的相邻移动。
• 每条边代价都是 1。
• 目标是从 S 到 T 的最短步数，并输出一条合法最短路。

BFS 处理无权图

什么时候用

• 每步代价一样。
• 只关心最少步数，不关心边权大小。
• 常见于网格、迷宫、层级传播、连通块扩展。

基本结构

from collections import deque

dist = [[-1] * w for _ in range(h)]
parent = [[None] * w for _ in range(h)]
queue = deque([(sx, sy)])
dist[sx][sy] = 0

while queue:
    x, y = queue.popleft()
    for dx, dy, mark in directions:
        nx, ny = x + dx, y + dy
        if not valid(nx, ny) or dist[nx][ny] != -1:
            continue
        dist[nx][ny] = dist[x][y] + 1
        parent[nx][ny] = (x, y, mark)
        queue.append((nx, ny))

为什么 BFS 得到的是最短步数

因为 BFS 按“层”扩展。第 0 层是起点，第 1 层是一步能到的点，第 2 层是两步能到的点。第一次访问到某个节点时，一定是用最少步数到达。

Dijkstra 处理带权图

什么时候用

• 边权非负。
• 总代价由多条边权累加而来。
• 希望求最小总时间、最小总代价、最小总风险。

基本结构

import heapq

dist = [INF] * (n + 1)
prev = [-1] * (n + 1)
dist[start] = 0
heap = [(0, start)]

while heap:
    cost, node = heapq.heappop(heap)
    if cost != dist[node]:
        continue
    for nxt, weight in graph[node]:
        new_cost = cost + weight
        if new_cost < dist[nxt]:
            dist[nxt] = new_cost
            prev[nxt] = node
            heapq.heappush(heap, (new_cost, nxt))

为什么要写 if cost != dist[node]

优先队列里可能会残留旧状态。这个判断的作用是丢掉已经过时的条目，避免重复扩展。

双关键字最短路

s3-jh-05 的重点不是只求最小总天数，而是先最小化换站次数，再在所有换站次数最少的方案里最小化总天数。此时每个节点的“距离”不再是一个整数，而是一对值：

• 第一关键字：边数 / 换站次数
• 第二关键字：总耗时

比较状态时，按字典序比 (steps, days) 即可。

典型写法

candidate = (steps + 1, days + weight)
if candidate < dist[nxt]:
    dist[nxt] = candidate
    prev[nxt] = node

这里的关键不是语法，而是想清楚：题目真正的“最优”到底由几个指标组成，指标顺序又是什么。

路径恢复怎么做

不管是 BFS 还是 Dijkstra，只要题目要求输出路径，就要额外记录“当前节点是从谁转移来的”。

常见记录方式

• 一维图：prev[node] = previous_node
• 网格图：parent[x][y] = (px, py, direction)
• 状态扩展图：parent[x][y][state] = 上一个状态

恢复步骤

1. 从终点开始回溯。
2. 一直跳到起点。
3. 把回溯得到的序列反转。

path = []
cur = target
while cur != -1:
    path.append(cur)
    cur = prev[cur]
path.reverse()

如果记录的是方向字符，那么回溯时把字符收集起来，最后再反转字符串。

字典序路径为什么要提前设计方向顺序

一些网格题不只要求最短路，还要求“若有多条最短路，输出字典序最小的那条”。这时你不能等 BFS 结束后再随便挑一条，必须在扩展邻居时就用固定方向顺序。

例如 s4-jh-07 固定 D < L < R < U，那么 BFS 扩展顺序也要按这个优先级来，这样第一次到达终点时，对应的就是按该优先级最小的最短路。

常见错误

把网格题当数组题做

如果题目里存在“可走 / 不可走 / 相邻移动 / 目标点”，本质上就是图，不要只盯着二维数组本身。

只记最小值，不记路径来源

最后得到最短距离后才想起要输出路径，通常就得重写。

用 BFS 处理有权图

只要边权不统一，BFS 就不能直接保证最优。

状态不完整

题目如果还跟资源、次数、是否经过某类点有关，只记录当前位置是不够的。

不可达判断漏掉

最短路题必须明确：终点如果没有被更新过，输出什么固定格式。

与题库的联系

s2-jh-01

• 练的是带权图最短路和前驱恢复。

s3-jh-05

• 练的是双关键字最短路，不是普通单关键字最短路。

s4-jh-07

• 练的是网格 BFS、方向顺序控制和路径字符串回溯。

训练建议

• 每做一道图题，先画一张只有 4 到 6 个点的小图手推。
• 写代码前先回答：我是要求步数、代价，还是带额外状态的最优值。
• 题目要求路径时，强制自己先定义 prev 或 parent 再写主循环。
• 如果结果不对，先打印 dist 和 prev，不要直接怀疑输出格式。