Lecture 16: 最短路径：Dijkstra 与 A（Shortest Paths: Dijkstra & A）（对应课程真实讲座 L26–L27）

目录 · ← l15 · l17 →

Lecture 16: 最短路径：Dijkstra 与 A（Shortest Paths: Dijkstra & A）（对应课程真实讲座 L26–L27）

概述

第 15 讲教会我们用 BFS 找“无权图”里边数最少的路径；本讲把问题升级为带权图上的最低代价路径（shortest path，代价 = 边权之和而非边数），主角是两个算法：Dijkstra（单源最短路径：从一个起点到图中所有顶点）与 A（单对最短路径：从起点到一个明确终点，靠启发式“抄近路”）。Dijkstra 的贪心直觉、堆优化运行时、负权边为何会“掀翻”它，以及 A 的 f = g + h 框架与可采纳启发式，是本讲核心。官方对应：L26（2026 年 8 月 6 日，周四，Dijkstra and A* Shortest Path Algorithms）与 L27（2026 年 8 月 10 日，周一，Graph Coding，课上用自建 WeightedGraph 类把拓扑排序与 Dijkstra 完整编码了一遍）。官方明确的口径：期末考试不要求手算走查 Dijkstra/A*，但要理解算法原理、三种找路算法的适用语境、以及堆优化带来的运行时差异；L27 编码课的内容（除“有环 ⇔ 无拓扑序”）不要求期末复现。

核心概念与算法原理

问题定义：单源最短路径（single-source shortest paths）。 给定带权有向/无向图与源点 source，求 source 到每个顶点的最低代价路径（“最短”在此指边权总和最小，不是边数最少）。应用：消息从一台主机最快广播到全网、货物从配送中心送往各目的地、疾病在社交网络上的扩散建模等。

Dijkstra 的直观解释（它是什么？）。 想象把每个顶点当成“会议地点”，dist[v] 是“目前已知从 source 到 v 的最低代价”。算法像一场逐级扩大的招标会：每次都把“当前已知代价最小、但尚未拍板”的顶点 u 拍板确定下来（它的 dist 从此封存不再改），然后用 u 的每条出边去“降价竞标”它的邻居——若走 u 再走一条边能比邻居现有报价更便宜，就更新报价。这个“永远先处理最便宜候选”的策略就是贪心。为什么确定后就可以封存？只要边权非负，任何“绕路”都必然先经过某个代价 ≥ dist[u] 的中间点，再加非负边，不可能更便宜——正是“非负权”让封存永远安全。

Dijkstra 操作/步骤分解（以邻接表 + dist/prev 数组为例）：

1. dist[source] = 0；其余 dist = ∞；prev[v] 记录前驱（用于回溯路径）
2. 反复执行，直到所有顶点确定（或用优先队列驱动到队空）：
   a. 挑出“未确定顶点中 dist 最小”的 u
      （朴素版：线性扫 dist 数组；堆优化版：从优先队列弹出）
   b. 标记 u 已确定
   c. 松弛（relaxation）：对 u 的每条边 (u, v, w)：
        若 v 未确定 且 dist[u] + w < dist[v]：
            dist[v] = dist[u] + w；prev[v] = u
3. 结束时 dist[v] 即 source 到 v 的最短代价；沿 prev 从 v 一路回溯到 source 得到路径

堆优化的关键技巧：“允许过期记录堆积”。 贪心地想把“挑最小 dist”交给优先队列，但标准的堆不支持“把已在堆里的元素改小”（decrease-key 很贵）。官方的解决方案非常直白：每次松弛成功就把新的 (dist[v], v) 整个压进堆，旧记录留在堆底不管——新记录更小，自然更快浮到堆顶；出堆时若发现该记录已过期（顶点早已确定，或记录的 dist 与当前 dist 不一致）就丢弃。代价是堆里会积累一些“垃圾”，但换来的是每轮“挑最小”从 O(n) 降到 O(log n)。

手算走查（5 个顶点，体会每一轮）。 图用邻接表给出（source = 0）：

邻接表（(邻居, 边权)）：
0: →(1,4) →(2,1)          2: →(0,1) →(1,2) →(3,5)
1: →(0,4) →(2,2) →(3,1) →(4,7)
3: →(1,1) →(2,5) →(4,3)   4: →(1,7) →(3,3)

结果：dist = {0, 3, 1, 4, 7}；最短路径 0→1 是 0-2-1（代价 3）而非直连 0→1（代价 4），0→4 是 0-2-1-3-4（代价 7）。注意第 2 轮正是 Dijkstra 的“神韵”所在：代价 4 的直连边已经摆在那，算法仍先确定了代价 1 的 2，因为 2 可能带来更便宜的绕路——贪心不是“抢近路”，而是“永远先封存当前最便宜的可能”。

为什么负权边会破坏 Dijkstra？ 负权推翻“确定后即可封存”的根基：一个已经确定（甚至已经确定很久）的顶点，可能因为某条带负权的边而出现更便宜的绕路，但算法不会再回头更新它。看这个三角形（A 为源点，边权 A→B=7、A→C=6、B→C=−3）：

A ──7──▶ B
│        │
│6       │ −3
▼        ▼
C ◀──────┘       真实最短路：A→B→C = 7 + (−3) = 4

Dijkstra 先确定 C（dist=6，比 B 的 7 小）；等 B 被确定（dist=7）时，它的邻居 C 已“封存”，松弛被跳过——最终 C 停在 6，永远错过了正确的 4。给所有边统一加一个常数把负权抹平也没用：加常数会改变不同长度路径的“相对差价”（官方补充材料里演示过这个错误修补方案）。官方补充：能处理负权的是 Bellman-Ford（反复对所有边松弛 n−1 轮，O(VE)），但它对负环（能无限循环变小代价的环）也无能为力——负环上的最短路径根本不存在。这部分在官方讲义里属于可选的补充阅读，期末不考。

A* 搜索（单对最短，带“指南针”）。 Dijkstra 有个“笨”处：它从源点朝所有方向均匀扩散，完全不管目标在哪个方向。A* 的改进是给每个节点加一个启发式 h(n)——从 n 到目标代价的“估计值”，并让优先级变成 f(n) = g(n) + h(n)，其中 g(n) 是从起点到 n 的真实代价。f 小 = “已经花得少 + 感觉离目标近”，于是搜索被“拽”向目标方向：

Dijkstra：以源点为圆心的圆形扩散          A*：偏向目标方向的锥形扩散
        · · · · ·                           · · · · ·
      · · · · · · ·                       · · · · · · ·
    · · · · S · · · ·                   · · · · S · · G
      · · · · · · ·                       · · · · · ·
        · · · · ·                           · · · · ·
   (对每个方向一视同仁)                (反方向探得少，更早碰到目标)

A* 伪代码（与 Dijkstra 逐行对照几乎只差优先级）：

1. g[start] = 0；把 (f = g + h, start) 压入优先队列
2. 弹出 f 最小的节点 n（过期记录直接丢弃）
3. 若 n 就是目标 → 沿 prev 回溯路径，结束
4. 对 n 的每个可达邻居 m：
      若 g[n] + 边权(n,m) < g[m]：
          g[m] = g[n] + 边权；prev[m] = n
          以 f = g[m] + h(m) 把 m 压入队列
5. 队列空仍未碰到目标 → 不可达

三个关键性质：① 可采纳（admissible）：h 永不高估到目标的真实代价。可采纳保证 A* 第一次弹出目标时即最优。② 一致（consistent/单调）：h(u) ≤ w(u,v) + h(v)。一致蕴含可采纳，还保证“节点一经确定不再回头处理”，实现与 Dijkstra 完全同构。③ h ≡ 0 时 A* 退化为 Dijkstra——所以 Dijkstra 可以看作“没有指南针的 A”。网格寻路常用曼哈顿距离、地图导航常用直线距离，二者均不高估。何时用不了 A：目标未知（如“在图里找藏起来的宝藏”）就没有 h 可算，只能 BFS/Dijkstra。官方在课上用可视化工具演示了三者的探索范围差异，并提供了斯坦福校友 Amit Patel 的 A* 专题资源供深入阅读。

三算法适用语境速查（官方期末考试点名的“哪类场景用哪个”）：

代码示例与实现详解

示例 1：Dijkstra 完整实现（邻接表 + std::priority_queue 小顶堆，输出距离与路径）。

#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

struct Edge { int to; int weight; };

// 单源最短路径：source 到每个顶点的最短代价写入 dist，路径前驱写入 prev
void dijkstra(int source, const vector<vector<Edge>>& adj,
              vector<int>& dist, vector<int>& prev) {
    int n = (int)adj.size();
    dist.assign(n, INT_MAX);
    prev.assign(n, -1);
    vector<bool> done(n, false);          // done[v]：v 的最短距离已封存

    // 小顶堆按 (dist, 顶点) 排序；允许旧记录滞留（lazy deletion）
    using P = pair<int, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (done[u]) continue;            // 过期记录：u 早已确定
        if (d != dist[u]) continue;       // 双保险：不是最新距离也跳过
        done[u] = true;                   // 此刻 u 的 dist 正式封存
        for (const Edge& e : adj[u]) {    // 松弛 u 的所有邻居
            int v = e.to;
            if (done[v]) continue;        // 已确定的顶点不再更新
            if (dist[u] + e.weight < dist[v]) {
                dist[v] = dist[u] + e.weight;   // 松弛成功：找到更便宜的路径
                prev[v] = u;
                pq.push({dist[v], v});    // 新记录入堆，旧记录自动作废
            }
        }
    }
}

// 递归回溯打印 source → v 的完整路径
void printPath(int v, const vector<int>& prev) {
    if (prev[v] == -1) { cout << v; return; }   // 到达 source
    printPath(prev[v], prev);
    cout << " → " << v;
}

int main() {
    int n = 5;
    vector<vector<Edge>> adj(n);          // 与手算走查同一张图
    auto add = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});         // 无向图：两条有向边
    };
    add(0, 1, 4); add(0, 2, 1); add(1, 2, 2);
    add(1, 3, 1); add(2, 3, 5); add(3, 4, 3); add(1, 4, 7);

    vector<int> dist, prev;
    dijkstra(0, adj, dist, prev);
    for (int v = 0; v < n; ++v) {
        cout << "到顶点 " << v << " 的最短代价 = "
             << (dist[v] == INT_MAX ? -1 : dist[v]) << "，路径: ";
        printPath(v, prev);
        cout << "\n";
    }
    return 0;
}

【代码做什么】 用与手算走查完全一致的图跑 Dijkstra，期望输出：到 1 代价 3 路径 0 → 2 → 1、到 4 代价 7 路径 0 → 2 → 1 → 3 → 4——把上文的表格在真实代码里复现一遍，是检验理解的黄金练习。

【实现机制解说】 ① 堆里存的 (dist, 顶点) 在松弛成功后不断有新版本入堆：某顶点可能同时存在多条不同 dist 的记录，但最小的那个一定先出堆——这正是“允许过期记录堆积”的实现形态；出堆时用 done[u] 与 d != dist[u] 两道检查滤掉垃圾。② dist[u] + e.weight 用 INT_MAX 会溢出：好在只有被松弛成功（有限值）的顶点才会入堆并出堆，出堆顶点必有有限 dist，因此加法安全；即便如此，习惯上仍可把初始值设为 INT_MAX/2 更稳妥。③ prev 前驱链在打印时必须先回溯到 source 再正向输出（递归天然做到），直接顺着 prev 打印得到的是反序路径。④ 无向图 = 每条边存两遍；有向图只存一遍，代码其余部分完全不变——算法本身不关心方向，只关心邻接表内容。

示例 2：A* 网格寻路（曼哈顿距离启发式）。

#include <algorithm>
#include <climits>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

const int dr[4] = {-1, 1, 0, 0};      // 上、下、左、右
const int dc[4] = {0, 0, -1, 1};

int manhattan(int r, int c, int gr, int gc) {
    return abs(r - gr) + abs(c - gc); // 启发式 h：最少还要走多少步（不高估）
}

// grid 中 0 可走、1 是障碍。找到 (sr,sc)→(tr,tc) 的最短路径写入 path。
bool aStar(const vector<vector<int>>& grid, int sr, int sc, int tr, int tc,
           vector<pair<int, int>>& path) {
    int R = (int)grid.size(), C = (int)grid[0].size();
    vector<vector<int>> g(R, vector<int>(C, INT_MAX / 2));  // 真实代价
    vector<vector<int>> prev(R, vector<int>(C, -1));        // 编码的前驱

    // 状态 (f, g, 行, 列)：按 f 升序，f 相同 g 小的先出（词典序天然如此）
    using State = tuple<int, int, int, int>;
    priority_queue<State, vector<State>, greater<State>> pq;
    g[sr][sc] = 0;
    pq.push({manhattan(sr, sc, tr, tc), 0, sr, sc});

    while (!pq.empty()) {
        auto [f, cost, r, c] = pq.top();
        pq.pop();
        if (r == tr && c == tc) {       // 目标第一次出堆 ⇒ 已是最优
            int cr = tr, cc = tc;
            while (!(cr == sr && cc == sc)) {
                path.push_back({cr, cc});
                int code = prev[cr][cc];      // 解出前驱坐标
                cr = code / C;
                cc = code % C;
            }
            path.push_back({sr, sc});
            reverse(path.begin(), path.end());
            return true;
        }
        if (cost != g[r][c]) continue;  // 过期记录
        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (grid[nr][nc] == 1) continue;          // 撞墙
            int ng = cost + 1;                        // 每步代价 1
            if (ng < g[nr][nc]) {
                g[nr][nc] = ng;
                prev[nr][nc] = r * C + c;             // 压缩存储前驱
                pq.push({ng + manhattan(nr, nc, tr, tc), ng, nr, nc});
            }
        }
    }
    return false;                       // 目标不可达
}

int main() {
    vector<vector<int>> grid = {        // 1 为障碍，S=(0,0)，G=(4,4)
        {0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0},
    };
    vector<pair<int, int>> path;
    bool ok = aStar(grid, 0, 0, 4, 4, path);
    if (!ok) { cout << "不可达\n"; return 0; }
    cout << "找到路径，长度 = " << path.size() - 1 << "\n";
    for (auto [r, c] : path) cout << "(" << r << "," << c << ") ";
    cout << "\n";
    return 0;
}

【代码做什么】 在 5×5 网格（含 4 块障碍）上从左上角寻路到右下角，输出最短路径的长度与逐点坐标。启发式取曼哈顿距离：它永远 ≤ 真实剩余步数（可采纳），且满足三角不等式（一致），因此“目标第一次出堆即最优”成立。把 manhattan 的调用全部换成返回 0 的函数，这个程序就退化成了逐格代价 1 的 Dijkstra——读者可以亲手改一行验证“A* ⊇ Dijkstra”的说法。

【实现机制解说】 ① 与示例 1 的唯一本质差异在优先级：Dijkstra 压 (g, 节点)，A* 压 (g + h, 节点)——f = g + h 不是新算法，而是“给 Dijkstra 换了个更聪明的排序键”。② h 可采纳时，任何“先出堆的目标”都不可能再被更便宜的绕路取代，因为那条绕路若存在，其 f 必然更小、会先出堆（与 Dijkstra 封存正确性同构的论证）。③ 前驱用 r*C+c 单个整数编码，省一个二维结构；回溯时除回去。④ 障碍迫使 A* “绕路”——最优路径有时会先朝远离目标的方向走几步再折返（先上高速再转弯），这恰是“偏置搜索但不禁止绕路”的设计意图，也是 h 只做估计、不做承诺的原因。

复杂度分析

设 V = 顶点数、E = 边数。dist/prev 数组空间 O(V)（邻接表另占 O(V+E)）。

易错点：堆优化的 O((V+E) log V) 是“把每次出堆/入堆算 O(log) 再乘以总次数”的直观结果；官方在讲义里专门提醒，像“连续 n 次插入堆”这类操作不能简单相乘——插入第 k 个元素的实际代价是 O(log k)，累加后才得到 O(n log n)（Stirling 近似）。同理，rehash/heapify 之类“看着像 O(n log n) 实则 O(n)”的反直觉结论，都源于对“操作对象规模在变化”的严谨求和——考试层面只需记住堆优化版把“挑最小”从 O(V) 降为 O(log V)。

关键要点

• Dijkstra 解决“单源 → 所有顶点”的带权最短路径，前提是边权非负；贪心“每次确定当前最小”之所以安全，正因为非负权让已确定者不可能被反超。
• 三种找路算法按场景选：无权用 BFS、带权单源用 Dijkstra、知道目标且能估代价用 A*；这是官方点名的期末考试判断题。
• 堆优化 Dijkstra 的正确姿势是“允许过期记录堆积”：松弛成功就把新 (dist, v) 整个入堆，出堆时丢弃已确定/过期条目——简单且有效。
• A* 只是给 Dijkstra 换了优先级 f = g + h；h 必须可采纳（永不高估）才保证最优，h ≡ 0 即退化为 Dijkstra。
• 负权边会让 Dijkstra 的“封存”失效；需要时用 Bellman-Ford（O(VE)），负环则根本无有限最短路。
• 官方期末口径：不要求手算走查 Dijkstra/A*，但原理、适用语境与堆优化运行时必须清楚。

常见陷阱与注意事项

• 在有负权边的图上跑 Dijkstra：得到的是错误答案且不易察觉。规避：确认边权非负；有负权改 Bellman-Ford。
• 给所有边加常数“抹平”负权：看似聪明实则无效（加常数改变长路径与短路径的相对差价，官方演示过失败例子）。规避：换算法，别修修补补。
• 堆里过期记录不丢弃：可能把已确定的顶点重复“处理”，甚至死循环。规避：出堆时检查 done 标记与 dist 是否仍是最新值。
• 松弛条件写反：写成 dist[v] + w < dist[u] 之类，结果全错。规避：牢记“老路 > 新路(u 经边到 v) 才更新”。
• 用 INT_MAX 当 ∞ 还直接加权重：溢出后变成负数，dist 表报废。规避：初始值用 INT_MAX/2，或仅在有限值时做加法。
• 路径打印顺序颠倒：沿 prev 回溯得到的是反序。规避：先递归到 source 再逐层输出（或存下再 reverse）。
• A* 用了不可采纳的启发式：可能“感觉很近”而错过真正的最优路径。规避：先验证 h 永不高估（网格用曼哈顿、地图用直线距离都安全）。
• 无权图也硬上 Dijkstra：能用，但 BFS 的 O(V+E) 更简单更快；反过来无权图中用 BFS 是标准答案。
• A* 用在“目标未知”的任务上：没有目标就没有 h。规避：目标不明的探索任务回归 BFS/Dijkstra。

思考题（带答案）

问题 1：为什么只要存在一条负权边，Dijkstra“确定后封存”的论证就崩溃？请用一句话概括其论证断点。 答案：Dijkstra 的封存依赖“任何绕路都要先经过一个 dist 不小于当前顶点、再加上非负边”的推理；负权边让“先绕到别处、再走负权边”可能比任何已确定的直达路径更便宜，而算法不会回头更新已封存的顶点——封存的前提被抽掉了。

问题 2：堆优化版 Dijkstra 中，为什么旧记录可以安心留在堆里不去删除？它最坏会让堆多大？ 答案：每次松弛成功都会产生一条更小的 (dist, v)，小记录必然先于同顶点的旧大记录出堆；旧记录出堆时用“已确定或 dist 不一致”直接丢弃，不影响正确性，只浪费一点堆空间。最坏情形（每轮几乎所有顶点都被反复改进）下堆里可能积累 O(V²) 条记录，对应官方给出的 O(V² log V) 上界；稀疏图上实际按松弛次数计，通常是 O((V+E) log V)。

问题 3：把 A* 的启发式分别设为“恒 0”“真实剩余代价”“可采纳但偶尔低估（永不高估）”，各会发生什么？ 答案：恒 0 → A* 退化为 Dijkstra，向所有方向扩散；等于真实代价 → 每个被展开的节点都在最优路径上，几乎“直线”冲到目标，探索最少；可采纳 → 保证首次弹出目标即最优，只是可能比“真实代价版”多探一些节点。若 h 偶尔高估（不可采纳），搜索会更快但结果可能不是最短——这是“速度”与“最优性”的交易。