当前位置：首页 > ds >正文

【考研408数据结构-09】图论进阶：最短路径与最小生成树

ds 2025/8/21 7:11:14

📚 【考研408数据结构-09】图论进阶：最短路径与最小生成树

🎯 考频：⭐⭐⭐⭐⭐ | 题型：选择题、综合应用题、算法设计题 | 分值：约10-18分

引言

想象你是一家物流公司的路线规划师。面对全国数百个配送站点，如何找到从总仓到各个站点的最短配送路径？如何用最少的成本连接所有站点构建配送网络？这些实际问题的本质就是图论中的最短路径和最小生成树问题。

在408考试中，最短路径和最小生成树算法是图论部分的核心考点，几乎每年必考。据统计，近5年的408真题中，Dijkstra算法出现7次，Prim/Kruskal算法出现6次，Floyd算法和关键路径也频繁出现在综合应用题中。这部分内容不仅分值高，而且是算法设计题的热门选择。

本文将深入剖析四大最短路径算法（Dijkstra、Floyd）和两大最小生成树算法（Prim、Kruskal），并掌握关键路径的求解方法。

学完本文，你将能够：

✅ 熟练掌握各算法的执行过程和实现细节
✅ 准确分析算法复杂度并选择合适算法
✅ 手工模拟算法执行步骤（408必考）
✅ 解决实际的网络优化问题

一、知识精讲

1.1 概念定义

最短路径问题

单源最短路径（Single-Source Shortest Path）：求一个顶点到其他所有顶点的最短路径

Dijkstra算法：适用于非负权图，贪心策略
Bellman-Ford算法：可处理负权边（408了解即可）

多源最短路径（All-Pairs Shortest Path）：求任意两顶点间的最短路径

Floyd-Warshall算法：动态规划思想，简洁高效

最小生成树（Minimum Spanning Tree, MST）：连通所有顶点且边权和最小的树

Prim算法：从顶点出发，逐步扩展
Kruskal算法：从边出发，逐步连接

关键路径（Critical Path）：AOE网中的最长路径，决定项目完成时间

⚠️ 408考纲要求：

掌握：Dijkstra、Prim、Kruskal算法
理解：Floyd算法、关键路径
了解：Bellman-Ford、SPFA算法

1.2 原理分析

1.2.1 Dijkstra算法原理

核心思想：贪心策略，每次选择当前最短的路径确定下来

初始化：源点距离为0，其他为∞
选择未确定的最短距离顶点u
更新u的邻接点距离（松弛操作）
重复直到所有顶点确定

关键点：

不能处理负权边（贪心选择的局限）
使用优先队列可优化到O(ElogV)

1.2.2 Floyd算法原理

核心思想：动态规划，考虑是否经过中间顶点k

状态定义：dist[i][j]表示i到j的最短距离
状态转移：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
三重循环：k为中间顶点，i、j为起终点

1.2.3 Prim算法原理

核心思想：从一个顶点开始，逐步扩展生成树

任选一个顶点加入MST
选择连接MST和非MST顶点的最小边
将该边和顶点加入MST
重复直到包含所有顶点

1.2.4 Kruskal算法原理

核心思想：按边权排序，逐个加入不构成环的边

将所有边按权值排序
依次选择最小边
若不构成环则加入MST（并查集判断）
直到选够n-1条边

1.3 性质与特点

算法	时间复杂度	空间复杂度	适用场景	408考频
Dijkstra	O(V²)或O(ElogV)	O(V)	单源非负权	⭐⭐⭐⭐⭐
Floyd	O(V³)	O(V²)	多源任意权	⭐⭐⭐⭐
Prim	O(V²)或O(ElogV)	O(V)	稠密图MST	⭐⭐⭐⭐
Kruskal	O(ElogE)	O(V)	稀疏图MST	⭐⭐⭐⭐⭐

算法选择策略：

单源最短路径：优先Dijkstra（非负权）
多源最短路径：Floyd（顶点少）
稠密图MST：Prim算法
稀疏图MST：Kruskal算法

二、代码实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>#define MAXV 100
#define INF INT_MAX// ========== 图的邻接矩阵表示 ==========
typedef struct {int vexnum, arcnum;int arcs[MAXV][MAXV];  // 边权矩阵char vexs[MAXV];
} MGraph;// ========== Dijkstra算法实现 ==========
void Dijkstra(MGraph *G, int src, int dist[], int path[]) {bool visited[MAXV];// 初始化for (int i = 0; i < G->vexnum; i++) {dist[i] = G->arcs[src][i];  // 初始距离visited[i] = false;          // 未访问path[i] = (dist[i] < INF) ? src : -1;  // 前驱}dist[src] = 0;visited[src] = true;// 主循环：找n-1个顶点的最短路径for (int i = 1; i < G->vexnum; i++) {int min = INF, u = -1;// 找未访问的最小距离顶点for (int j = 0; j < G->vexnum; j++) {if (!visited[j] && dist[j] < min) {min = dist[j];u = j;}}if (u == -1) break;  // 无可达顶点visited[u] = true;// 松弛操作：更新u的邻接点距离for (int v = 0; v < G->vexnum; v++) {if (!visited[v] && G->arcs[u][v] < INF) {if (dist[u] + G->arcs[u][v] < dist[v]) {dist[v] = dist[u] + G->arcs[u][v];path[v] = u;  // 更新前驱}}}}
}// 打印最短路径
void PrintPath(int path[], int v) {if (path[v] == -1) {printf("无路径");return;}int stack[MAXV], top = -1;while (v != -1) {stack[++top] = v;v = path[v];if (top > 0 && v == stack[top-1]) break;  // 避免死循环}while (top >= 0) {printf("%d ", stack[top--]);if (top >= 0) printf("-> ");}
}// ========== Floyd算法实现 ==========
void Floyd(MGraph *G, int dist[][MAXV], int path[][MAXV]) {// 初始化for (int i = 0; i < G->vexnum; i++) {for (int j = 0; j < G->vexnum; j++) {dist[i][j] = G->arcs[i][j];path[i][j] = (G->arcs[i][j] < INF && i != j) ? i : -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 (dist[i][k] != INF && dist[k][j] != INF) {if (dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];path[i][j] = path[k][j];  // 更新前驱}}}}}
}// ========== Prim算法实现 ==========
int Prim(MGraph *G, int start) {int lowcost[MAXV];  // 到MST的最小代价int closest[MAXV];  // 最近的MST顶点bool inMST[MAXV];   // 是否在MST中int sum = 0;        // MST权值和// 初始化for (int i = 0; i < G->vexnum; i++) {lowcost[i] = G->arcs[start][i];closest[i] = start;inMST[i] = false;}inMST[start] = true;// 选择n-1条边for (int i = 1; i < G->vexnum; i++) {int min = INF, k = -1;// 找最小边for (int j = 0; j < G->vexnum; j++) {if (!inMST[j] && lowcost[j] < min) {min = lowcost[j];k = j;}}if (k == -1) return -1;  // 图不连通printf("边(%d,%d) 权值:%d\n", closest[k], k, min);sum += min;inMST[k] = true;// 更新lowcostfor (int j = 0; j < G->vexnum; j++) {if (!inMST[j] && G->arcs[k][j] < lowcost[j]) {lowcost[j] = G->arcs[k][j];closest[j] = k;}}}return sum;
}// ========== Kruskal算法（使用并查集）==========
typedef struct {int u, v, w;  // 边的两个顶点和权值
} Edge;// 并查集查找
int Find(int parent[], int x) {if (parent[x] != x) {parent[x] = Find(parent, parent[x]);  // 路径压缩}return parent[x];
}// 并查集合并
void Union(int parent[], int rank[], int x, int y) {int rootX = Find(parent, x);int rootY = Find(parent, y);if (rootX != rootY) {if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else {parent[rootY] = rootX;rank[rootX]++;}}
}// 边的比较函数（用于排序）
int compareEdge(const void *a, const void *b) {return ((Edge*)a)->w - ((Edge*)b)->w;
}int Kruskal(MGraph *G, Edge edges[], int edgeNum) {int parent[MAXV], rank[MAXV];int sum = 0, count = 0;// 初始化并查集for (int i = 0; i < G->vexnum; i++) {parent[i] = i;rank[i] = 0;}// 边按权值排序qsort(edges, edgeNum, sizeof(Edge), compareEdge);// 依次选择边for (int i = 0; i < edgeNum && count < G->vexnum - 1; i++) {int u = edges[i].u;int v = edges[i].v;// 判断是否构成环if (Find(parent, u) != Find(parent, v)) {printf("选择边(%d,%d) 权值:%d\n", u, v, edges[i].w);Union(parent, rank, u, v);sum += edges[i].w;count++;}}return (count == G->vexnum - 1) ? sum : -1;  // 判断是否连通
}// ========== 关键路径算法 ==========
typedef struct {int ve[MAXV];  // 事件最早发生时间int vl[MAXV];  // 事件最晚发生时间
} CriticalPath;bool TopologicalSort_CP(MGraph *G, int ve[], int stack[]) {int indegree[MAXV] = {0};int queue[MAXV], front = 0, rear = 0;int count = 0, top = -1;// 计算入度for (int i = 0; i < G->vexnum; i++) {for (int j = 0; j < G->vexnum; j++) {if (G->arcs[i][j] < INF && G->arcs[i][j] > 0) {indegree[j]++;}}}// 初始化vefor (int i = 0; i < G->vexnum; i++) {ve[i] = 0;if (indegree[i] == 0) {queue[rear++] = i;}}// 拓扑排序并计算vewhile (front != rear) {int u = queue[front++];stack[++top] = u;  // 记录拓扑序列count++;for (int v = 0; v < G->vexnum; v++) {if (G->arcs[u][v] < INF && G->arcs[u][v] > 0) {indegree[v]--;if (ve[u] + G->arcs[u][v] > ve[v]) {ve[v] = ve[u] + G->arcs[u][v];}if (indegree[v] == 0) {queue[rear++] = v;}}}}return count == G->vexnum;
}void CriticalPathMethod(MGraph *G) {int ve[MAXV], vl[MAXV];int stack[MAXV], top = -1;// 拓扑排序并计算veif (!TopologicalSort_CP(G, ve, stack)) {printf("图中存在环，无法计算关键路径\n");return;}top = G->vexnum - 1;// 初始化vl为ve[n-1]for (int i = 0; i < G->vexnum; i++) {vl[i] = ve[G->vexnum - 1];}// 逆拓扑序计算vlwhile (top >= 0) {int u = stack[top--];for (int v = 0; v < G->vexnum; v++) {if (G->arcs[u][v] < INF && G->arcs[u][v] > 0) {if (vl[v] - G->arcs[u][v] < vl[u]) {vl[u] = vl[v] - G->arcs[u][v];}}}}// 输出关键活动printf("关键活动：\n");for (int u = 0; u < G->vexnum; u++) {for (int v = 0; v < G->vexnum; v++) {if (G->arcs[u][v] < INF && G->arcs[u][v] > 0) {int e = ve[u];  // 活动最早开始时间int l = vl[v] - G->arcs[u][v];  // 活动最晚开始时间if (e == l) {printf("<%d,%d> ", u, v);}}}}
}

复杂度分析：

Dijkstra：O(V²)，堆优化后O(ElogV)
Floyd：O(V³)，空间O(V²)
Prim：O(V²)，堆优化后O(ElogV)
Kruskal：O(ElogE)，主要是排序时间

三、图解说明

【图1】Dijkstra算法执行过程

初始图（源点0）:1 --3-- 3/|       |\2 |       | 1/  |       |  \
0   2       4   5\  |       |  /1 |       | 2\|       |/2 --3-- 4步骤1: dist=[0,2,1,∞,∞,∞] 选择顶点2
步骤2: dist=[0,2,1,5,3,∞] 选择顶点1  
步骤3: dist=[0,2,1,5,3,∞] 选择顶点4
步骤4: dist=[0,2,1,5,3,6] 选择顶点3
步骤5: dist=[0,2,1,4,3,5] 选择顶点5最短路径树:0/ \2   4|   |1   3--5

【图2】Prim算法构建MST

步骤1: 选择顶点0        步骤2: 选边(0,2)权1      步骤3: 选边(2,1)权20                       0                         0/                         /2                          2---1步骤4: 选边(0,4)权1     步骤5: 选边(1,3)权30                       0/ \                     / \2   4                   2   4|                       |1                       1---3MST总权值: 1+1+2+3=7

【图3】Floyd算法状态转移

初始矩阵D⁰:          经过顶点0后D¹:        经过顶点0,1后D²:
[0  5  ∞]           [0  5  ∞]            [0  5  8]
[5  0  3]           [5  0  3]            [5  0  3]
[∞  3  0]           [∞  3  0]            [8  3  0]状态转移: D[i][j] = min(D[i][j], D[i][k]+D[k][j])

【图4】关键路径示例

AOE网:v1 --a3(6)-- v3/  \          / \
a1(3)  a2(2)  a5(1) a7(2)/      \    /      \
v0      v2--a4(3)    v5\               /---a6(4)-- v4--a8(1)ve: [0,3,2,6,4,7]  (最早发生时间)
vl: [0,4,3,6,4,7]  (最晚发生时间)关键活动: a1,a5,a7 (e=l的活动)
关键路径: v0->v1->v3->v5 (长度=8)

四、真题演练

📝 真题1（2023年408第42题）

题目：给定带权有向图G，使用Dijkstra算法求顶点0到其他顶点的最短路径。当有多条最短路径时，要求输出经过顶点数最少的那条。请修改算法实现此要求。

解题思路：

在原Dijkstra基础上增加count[]数组记录路径顶点数
当发现相同最短距离时，选择顶点数更少的路径
松弛操作时同时更新count数组

参考答案：

if (dist[u] + G->arcs[u][v] < dist[v]) {dist[v] = dist[u] + G->arcs[u][v];path[v] = u;count[v] = count[u] + 1;
} else if (dist[u] + G->arcs[u][v] == dist[v]) {if (count[u] + 1 < count[v]) {path[v] = u;count[v] = count[u] + 1;}
}

易错点：

⚠️ 忘记初始化count数组
⚠️ 相等情况的判断条件写错

📝 真题2（2022年408算法设计题）

题目：设计算法判断无向图G是否存在一棵包含所有顶点的生成树，如果存在，求出权值最小的生成树的权值和。

解题思路：

先判断图的连通性（DFS或并查集）
若连通，使用Kruskal或Prim求MST
返回MST的权值和

评分要点：

连通性判断（3分）
MST算法实现（5分）
复杂度分析（2分）

📝 真题3（2021年408第23题）

题目：已知AOE网的关键路径长度为18，下列哪个活动一定是关键活动？
A. 最早开始时间为0的活动
B. 最晚开始时间为18的活动
C. 最早开始时间等于最晚开始时间的活动
D. 持续时间最长的活动

答案：C

解析：关键活动的充要条件是e(i)=l(i)，即最早开始时间等于最晚开始时间。A、B、D都不是充分条件。

五、在线练习推荐

LeetCode精选题目

743. 网络延迟时间（Medium，Dijkstra）
787. K站中转内最便宜的航班（Medium，最短路径变形）
1135. 最低成本连通所有城市（Medium，MST）
1584. 连接所有点的最小费用（Medium，Kruskal/Prim）

牛客网408专项

最短路径算法专项训练
最小生成树真题集

ACM经典题目

POJ 2387 - Til the Cows Come Home（Dijkstra模板）
POJ 1287 - Networking（MST模板）

练习顺序建议

先练习单源最短路径（Dijkstra）
掌握MST基础题（Prim/Kruskal）
进阶到Floyd多源最短路径
最后练习关键路径综合题

六、思维导图

图论进阶算法
├── 最短路径
│   ├── 单源最短路径
│   │   ├── Dijkstra算法
│   │   │   ├── 贪心策略
│   │   │   ├── 非负权图
│   │   │   └── O(V²)/O(ElogV)
│   │   └── Bellman-Ford
│   │       └── 可处理负权
│   └── 多源最短路径
│       └── Floyd算法
│           ├── 动态规划
│           ├── 三重循环
│           └── O(V³)
├── 最小生成树
│   ├── Prim算法
│   │   ├── 从顶点扩展
│   │   ├── 贪心选择
│   │   └── 适合稠密图
│   └── Kruskal算法
│       ├── 从边选择
│       ├── 并查集判环
│       └── 适合稀疏图
└── 关键路径├── AOE网├── ve/vl计算├── 关键活动└── 项目管理应用