408

数据结构

最短路径（Dijkstra/Floyd）

---

一、定位信息

• 圈层：核心层（大纲考点）
• 前置知识：图的基本概念（有向网/无向网、权、路径长度）、图的存储（邻接矩阵）、数组的基本操作。
• 知识网络定位：最短路径是图论中的核心优化问题，Dijkstra 解决单源最短路径，Floyd 解决所有顶点对之间的最短路径，是贪心和动态规划思想在图论中的经典应用。
• 考点热度：H级（高频重点） — 近 5 年真题中出现 ≥4 次，Dijkstra 算法的手算过程是高频考点，单次分值 5–10 分。

---

二、知识点讲解

2.1 最短路径问题分类

• 单源最短路径：从一个源点出发，到其余所有顶点的最短路径。解法：Dijkstra 算法（适用于非负权图）。
• 所有顶点对之间的最短路径：任意两个顶点之间的最短路径。解法：Floyd 算法（适用于任意权图，但不能有负权回路）。

2.2 Dijkstra 算法

核心思想：贪心策略。维护两个集合 $S$（已确定最短路径的顶点集）和 $V - S$（尚未确定的顶点集）。每次从 $V - S$ 中选距离源点最近的顶点加入 $S$，并用该顶点更新其余顶点的距离。

算法步骤：

1. 初始化：源点 $s$ 的距离 $dist[s] = 0$，其余顶点 $dist[v] = \infty$。$S = \emptyset$。
2. 从 $V - S$ 中选 $dist$ 值最小的顶点 $u$，将 $u$ 加入 $S$。
3. 用 $u$ 对 $V - S$ 中的所有邻接顶点 $v$ 进行松弛操作： $\text{if } dist[u] + w(u, v) < dist[v] \text{ then } dist[v] = dist[u] + w(u, v)$
4. 重复步骤 2–3，直到 $S = V$。

伪代码：

void Dijkstra(MGraph G, int s) {
    // 求源点 s 到所有顶点的最短路径
    bool S[MAX_VERTEX_NUM];     // S[i]=true 表示顶点 i 已确定最短路径
    int dist[MAX_VERTEX_NUM];   // dist[i] 表示当前 s 到 i 的最短距离估计
    int path[MAX_VERTEX_NUM];   // path[i] 表示 s 到 i 的最短路径上 i 的前驱
    
    for (int i = 0; i < G.vexnum; i++) {
        S[i] = false;                // 初始：所有顶点不在 S 中
        dist[i] = G.arc[s][i];      // 初始距离：s 到各顶点的直接边权
        if (dist[i] < INF)
            path[i] = s;             // 有边则前驱为 s
        else
            path[i] = -1;            // 无边则无前驱
    }
    S[s] = true;                     // 源点加入 S
    dist[s] = 0;                     // 源点到自身距离为 0
    
    for (int i = 1; i < G.vexnum; i++) {
        // 再加入 n-1 个顶点
        int min = INF, u = -1;
        for (int j = 0; j < G.vexnum; j++) {
            // 从 V-S 中选 dist 最小的顶点
            if (!S[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        S[u] = true;                 // u 加入 S
        
        for (int j = 0; j < G.vexnum; j++) {
            // 松弛操作：用 u 更新 V-S 中顶点的距离
            if (!S[j] && dist[u] + G.arc[u][j] < dist[j]) {
                dist[j] = dist[u] + G.arc[u][j];  // 更新距离
                path[j] = u;                       // 更新前驱
            }
        }
    }
}

时间复杂度：$O(n^2)$（两层循环）。

重要限制：Dijkstra 算法不能处理负权边。因为一旦某个顶点加入 $S$，其最短距离就不再更新，而负权边可能导致后续发现更短路径。

2.3 Floyd 算法

核心思想：动态规划。设 $D^{(k)}[i][j]$ 表示从 $v_i$ 到 $v_j$、中间顶点编号不超过 $k$ 的最短路径长度。

状态转移方程：

$$D^{(k)}[i][j] = \min\left(D^{(k-1)}[i][j], \quad D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\right)$$

含义：从 $v_i$ 到 $v_j$ 的最短路径，要么不经过 $v_k$（$D^{(k-1)}[i][j]$），要么经过 $v_k$（$D^{(k-1)}[i][k] + D^{(k-1)}[k][j]$），取两者中的较小值。

算法步骤：

1. 初始化：$D^{(0)}[i][j]$ = 邻接矩阵 $A[i][j]$（直接边权，无边为 $\infty$，对角线为 0）。
2. 对 $k = 0, 1, \dots, n-1$，依次更新： $D[i][j] = \min(D[i][j], \quad D[i][k] + D[k][j])$
3. 最终 $D[i][j]$ 即为 $v_i$ 到 $v_j$ 的最短路径长度。

伪代码：

void Floyd(MGraph G) {
    int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 最短距离矩阵
    int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 前驱矩阵
    
    // 初始化
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            D[i][j] = G.arc[i][j];        // 初始为邻接矩阵
            if (i != j && G.arc[i][j] < INF)
                path[i][j] = i;            // 有边则前驱为 i
            else
                path[i][j] = -1;           // 无边
        }
    }
    
    // 核心：三重循环，k 在最外层
    for (int k = 0; k < G.vexnum; k++) {        // 中间顶点
        for (int i = 0; i < G.vexnum; i++) {    // 起点
            for (int j = 0; j < G.vexnum; j++) {// 终点
                if (D[i][k] + D[k][j] < D[i][j]) {
                    // 经过 k 更短，更新
                    D[i][j] = D[i][k] + D[k][j];
                    path[i][j] = path[k][j];   // 更新前驱
                }
            }
        }
    }
}

时间复杂度：$O(n^3)$（三重循环）。

优点：代码简洁，能处理负权边（但不能有负权回路），能同时求出所有顶点对的最短路径。

2.4 松弛操作（Relaxation）

松弛是 Dijkstra 和 Floyd 的核心操作。对于边 $(u, v)$： $\text{if } dist[u] + w(u, v) < dist[v] \text{ then } dist[v] = dist[u] + w(u, v)$

直观理解：如果"经过 $u$ 到达 $v$"比"当前已知的到 $v$ 的路径"更短，就更新距离。

2.5 Dijkstra 完整执行示例

示例图：

【图示说明】有向网有 5 个顶点 $v_0, v_1, v_2, v_3, v_4$。弧及权值：$\langle v_0,v_1 \rangle 10, \langle v_0,v_3 \rangle 30, \langle v_0,v_4 \rangle 100, \langle v_1,v_2 \rangle 50, \langle v_2,v_4 \rangle 10, \langle v_3,v_2 \rangle 20, \langle v_3,v_4 \rangle 60$。源点为 $v_0$。

执行过程：

步骤	$S$	选出 $u$	$dist$ 更新	$dist[0]$	$dist[1]$	$dist[2]$	$dist[3]$	$dist[4]$
初始	$\{v_0\}$	—	初始化	0	10	$\infty$	30	100
1	$\{v_0,v_1\}$	$v_1$	$v_1$ 的邻接点 $v_2$: $10+50=60 < \infty$	0	10	60	30	100
2	$\{v_0,v_1,v_3\}$	$v_3$	$v_3$ 的邻接点 $v_2$: $30+20=50 < 60$; $v_4$: $30+60=90 < 100$	0	10	50	30	90
3	$\{v_0,v_1,v_3,v_2\}$	$v_2$	$v_2$ 的邻接点 $v_4$: $50+10=60 < 90$	0	10	50	30	60
4	$\{v_0,v_1,v_3,v_2,v_4\}$	$v_4$	无未访问邻接点	0	10	50	30	60

最终结果：$v_0$ 到各顶点的最短距离：$v_0:0, v_1:10, v_2:50, v_3:30, v_4:60$。

---

三、记忆与理解辅助

技巧 1：Dijkstra vs Floyd 对比表

对比维度	Dijkstra	Floyd
问题类型	单源最短路径	所有顶点对最短路径
算法思想	贪心	动态规划
时间复杂度	$O(n^2)$	$O(n^3)$
负权边	不支持	支持（无负权回路）
适用场景	求一个源点到其他点的最短路	求任意两点间最短路
代码复杂度	中等	简洁（核心仅 3 行）
循环结构	两层循环	三层循环（k 在最外层）

技巧 2：口诀

• "Dijkstra 贪心选最近，松弛更新不支持负"
• "Floyd 三层 k 在外，动态规划求全局"
• "松弛操作：经过 u 到 v 更短就更新"

技巧 3：Floyd 三重循环顺序

• k 必须在最外层！这是 Floyd 正确性的关键。
• 如果 k 不在最外层，则 $D[i][k]$ 和 $D[k][j]$ 可能还未被正确更新。
• 记忆："k 在外，i 在中，j 在内"。

技巧 4：path 矩阵的含义

• Dijkstra 中 path[v] = 最短路径上 $v$ 的前驱顶点。
• Floyd 中 path[i][j] = 从 $v_i$ 到 $v_j$ 的最短路径上 $v_j$ 的前驱顶点。
• 通过 path 可以回溯出完整路径。

---

四、例题与精解

例题 1（基础巩固 — Dijkstra 手算）

题目：对下图所示的有向网，用 Dijkstra 算法求 $v_0$ 到所有顶点的最短路径，写出每步的 $dist$ 数组变化和最终路径。

【图示说明】4 个顶点 $v_0, v_1, v_2, v_3$。弧：$\langle v_0,v_1 \rangle 1, \langle v_0,v_2 \rangle 4, \langle v_1,v_2 \rangle 2, \langle v_1,v_3 \rangle 6, \langle v_2,v_3 \rangle 3$。

命题意图：考查 Dijkstra 算法的完整执行过程。

完整步骤：

步骤	$S$	选出 $u$	松弛操作	$dist[0]$	$dist[1]$	$dist[2]$	$dist[3]$
初始	$\{v_0\}$	—	—	0	1	4	$\infty$
1	$\{v_0,v_1\}$	$v_1$	$v_2$: $1+2=3<4$✓; $v_3$: $1+6=7<\infty$✓	0	1	3	7
2	$\{v_0,v_1,v_2\}$	$v_2$	$v_3$: $3+3=6<7$✓	0	1	3	6
3	$\{v_0,v_1,v_2,v_3\}$	$v_3$	无	0	1	3	6

最终结果：

• $v_0 \to v_1$：$v_0 \to v_1$，距离 1
• $v_0 \to v_2$：$v_0 \to v_1 \to v_2$，距离 3
• $v_0 \to v_3$：$v_0 \to v_1 \to v_2 \to v_3$，距离 6

---

例题 2（中等提升 — Floyd 手算）

题目：对下图所示的有向网，用 Floyd 算法求所有顶点对之间的最短路径，写出 $D$ 矩阵的每步变化。

【图示说明】3 个顶点 $v_0, v_1, v_2$。弧：$\langle v_0,v_1 \rangle 4, \langle v_0,v_2 \rangle 11, \langle v_1,v_0 \rangle 6, \langle v_1,v_2 \rangle 2, \langle v_2,v_0 \rangle 3$。

命题意图：考查 Floyd 算法的完整执行过程和对三重循环的理解。

完整步骤：

初始 $D^{(0)}$（邻接矩阵）：

	$v_0$	$v_1$	$v_2$
$v_0$	0	4	11
$v_1$	6	0	2
$v_2$	3	$\infty$	0

$k=0$（考虑经过 $v_0$ 的路径）：

• $D[1][0]+D[0][2] = 6+11 = 17 > 2 = D[1][2]$，不更新
• $D[2][0]+D[0][1] = 3+4 = 7 < \infty = D[2][1]$，更新 $D[2][1] = 7$

$D^{(1)}$：

	$v_0$	$v_1$	$v_2$
$v_0$	0	4	11
$v_1$	6	0	2
$v_2$	3	7	0

$k=1$（考虑经过 $v_0, v_1$ 的路径）：

• $D[0][1]+D[1][2] = 4+2 = 6 < 11 = D[0][2]$，更新 $D[0][2] = 6$
• $D[2][1]+D[1][0] = 7+6 = 13 > 3 = D[2][0]$，不更新
• $D[2][1]+D[1][2] = 7+2 = 9 > 0$，不更新
• $D[0][1]+D[1][0] = 4+6 = 10 > 0$，不更新

$D^{(2)}$：

	$v_0$	$v_1$	$v_2$
$v_0$	0	4	6
$v_1$	6	0	2
$v_2$	3	7	0

$k=2$（考虑经过 $v_0, v_1, v_2$ 的路径）：

• $D[0][2]+D[2][1] = 6+7 = 13 > 4$，不更新
• $D[1][2]+D[2][0] = 2+3 = 5 < 6 = D[1][0]$，更新 $D[1][0] = 5$
• 其余组合均不产生更短路径。

$D^{(3)}$（最终结果）：

	$v_0$	$v_1$	$v_2$
$v_0$	0	4	6
$v_1$	5	0	2
$v_2$	3	7	0

方法反思：Floyd 算法的每一步 $k$ 表示"允许经过编号 $\leq k$ 的顶点"。注意 $k$ 必须在最外层，否则结果不正确。

---

五、考情分析

• 考查频次：近 5 年真题中出现 ≥4 次，是图论部分的核心考点。
• 常见题型：选择题（算法对比、时间复杂度）、综合应用题（手算 Dijkstra/Floyd 执行过程、代码填空）。
• 分值占比：选择题 2 分，综合题 5–10 分。
• 命题趋势：Dijkstra 手算是高频大题，Floyd 手算也时有出现。近年来增加了对"松弛操作"理解和负权边处理的考查。
• 基于大纲与命题规律推测

---

六、易错点提醒

1. 错误表现：Dijkstra 算法中，选出了 $u$ 加入 $S$ 后，忘记用 $u$ 来松弛其他顶点。 错误原因：Dijkstra 的正确性依赖于"每次选出最近顶点后，用它来更新其他顶点的距离"。 正确做法：选出 $u$ 后，立即对所有邻接顶点执行松弛操作。

2. 错误表现：Floyd 算法中将 $k$ 放在最内层循环。 错误原因：$k$ 在最内层时，$D[i][k]$ 和 $D[k][j]$ 可能还未被更新为考虑了中间顶点 $k$ 的最短路径，导致结果错误。 正确做法：$k$ 必须在最外层，确保每轮 $k$ 的更新建立在上一轮的基础上。

3. 错误表现：对含负权边的图使用 Dijkstra 算法。 错误原因：Dijkstra 基于贪心策略，假设已加入 $S$ 的顶点距离不会再变小。负权边可能在后续发现更短路径，打破这一假设。 正确做法：有负权边时，使用 Bellman-Ford 或 Floyd 算法。

4. 错误表现：Floyd 算法中，$D[i][i]$（对角线）被错误更新。 错误原因：$D[i][i]$ 表示顶点到自身的距离，应始终为 0。如果图有负权回路，$D[i][i]$ 可能变为负数，说明存在负权回路。 正确做法：初始化 $D[i][i] = 0$，最终若 $D[i][i] < 0$，说明存在经过 $v_i$ 的负权回路。

---

七、来源标注

• 依据 2026 考研统考大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据大学本科经典教材共识