【数据结构与算法】第40篇：图论（四）：最短路径——Dijkstra算法与Floyd算法

一、最短路径问题概述

1.1 问题定义

给定带权图，找出两个顶点之间权值之和最小的路径。

分类：

• 单源最短路径：一个起点到其他所有点的最短路径

• 多源最短路径：任意两点之间的最短路径

1.2 应用场景

二、Dijkstra算法

2.1 算法思想

Dijkstra算法是贪心算法，从起点开始，每次选择距离起点最近且未处理的顶点，然后松弛它的邻接边。

限制：不能处理负权边（因为贪心假设已找到最短路径不再更新）。

步骤：

2.2 图解示例

text

图结构：
1
0 — 1 (4)
| / \\
(2) (1) (5)
| / \\
2 — 3 — 4
(3) (2)

从0开始：
初始：dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞, dist[4]=∞

选0：松弛邻接点
dist[1]=2, dist[2]=1
visited: {0}

选2（dist=1）：松弛
dist[3]=1+3=4
visited: {0,2}

选1（dist=2）：松弛
dist[3]=min(4, 2+5)=4, dist[4]=2+?（无直接边）
visited: {0,2,1}

选3（dist=4）：松弛
dist[4]=4+2=6
visited: {0,2,1,3}

选4（dist=6）：无松弛
完成

2.3 代码实现

c

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX

// Dijkstra算法（邻接矩阵）
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int n, int start) {
int dist[MAX_VERTICES];
int visited[MAX_VERTICES] = {0};
int prev[MAX_VERTICES]; // 记录前驱节点，用于还原路径

// 初始化
for (int i = 0; i < n; i++) {
dist[i] = INF;
prev[i] = -1;
}
dist[start] = 0;

for (int count = 0; count < n – 1; count++) {
// 找到未处理中距离最小的顶点
int u = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
u = i;
}
}

if (dist[u] == INF) break; // 剩余顶点不可达

visited[u] = 1;

// 松弛邻接边
for (int v = 0; v < n; v++) {
if (graph[u][v] != INF && !visited[v] &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
prev[v] = u;
}
}
}

// 输出结果
printf("起点 %d 到各点的最短距离:\\n", start);
for (int i = 0; i < n; i++) {
if (dist[i] == INF) {
printf(" %d: 不可达\\n", i);
} else {
printf(" %d: %d", i, dist[i]);
// 打印路径（可选）
if (i != start) {
printf(" (路径: %d", i);
int p = prev[i];
while (p != -1) {
printf(" <- %d", p);
p = prev[p];
}
printf(")");
}
printf("\\n");
}
}
}

int main() {
int n = 5;
int graph[MAX_VERTICES][MAX_VERTICES];

// 初始化无穷大
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = (i == j) ? 0 : INF;
}
}

// 添加边
graph[0][1] = graph[1][0] = 2;
graph[0][2] = graph[2][0] = 1;
graph[1][2] = graph[2][1] = 1;
graph[1][3] = graph[3][1] = 5;
graph[2][3] = graph[3][2] = 3;
graph[3][4] = graph[4][3] = 2;

dijkstra(graph, n, 0);

return 0;
}

运行结果：

text

起点 0 到各点的最短距离:
0: 0
1: 2 (路径: 1 <- 0)
2: 1 (路径: 2 <- 0)
3: 4 (路径: 3 <- 2 <- 0)
4: 6 (路径: 4 <- 3 <- 2 <- 0)

2.4 堆优化版（适合稀疏图）

c

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 1000
#define INF INT_MAX

// 优先队列节点
typedef struct {
int vertex;
int dist;
} Node;

// 简单堆实现（这里用数组模拟，实际可用二叉堆）
// 实际工程中建议用二叉堆或优先队列

void dijkstraHeap(int graph[MAX_VERTICES][MAX_VERTICES], int n, int start) {
int dist[MAX_VERTICES];
int visited[MAX_VERTICES] = {0};

for (int i = 0; i < n; i++) dist[i] = INF;
dist[start] = 0;

for (int count = 0; count < n; count++) {
int u = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
u = i;
}
}
if (dist[u] == INF) break;
visited[u] = 1;

for (int v = 0; v < n; v++) {
if (graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// 输出…
}

三、Floyd算法

3.1 算法思想

Floyd算法是动态规划思想：逐步允许经过更多顶点作为中间点，更新最短路径。

核心公式：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

步骤：

3.2 动态规划推导

状态定义：dp[k][i][j] 表示允许经过前k个顶点时，i到j的最短路径

状态转移：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

空间优化：可以只用二维数组，k循环在外层。

3.3 代码实现

c

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX

// Floyd算法
void floyd(int graph[MAX_VERTICES][MAX_VERTICES], int n) {
int dist[MAX_VERTICES][MAX_VERTICES];
int next[MAX_VERTICES][MAX_VERTICES]; // 记录路径

// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
if (graph[i][j] != INF && i != j) {
next[i][j] = j;
} else {
next[i][j] = -1;
}
}
}

// Floyd核心：三重循环
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
}
}

// 输出结果
printf("任意两点之间的最短距离:\\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
printf(" %d到%d: 0\\n", i, j);
} else if (dist[i][j] == INF) {
printf(" %d到%d: 不可达\\n", i, j);
} else {
printf(" %d到%d: %d", i, j, dist[i][j]);
// 打印路径
if (next[i][j] != -1) {
printf(" (路径: %d", i);
int p = next[i][j];
while (p != j) {
printf(" -> %d", p);
p = next[p][j];
}
printf(" -> %d)", j);
}
printf("\\n");
}
}
printf("\\n");
}
}

int main() {
int n = 4;
int graph[MAX_VERTICES][MAX_VERTICES];

// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = (i == j) ? 0 : INF;
}
}

// 添加边
graph[0][1] = 5;
graph[0][3] = 10;
graph[1][2] = 3;
graph[2][3] = 1;

floyd(graph, n);

return 0;
}

运行结果：

text

任意两点之间的最短距离:
0到0: 0
0到1: 5 (路径: 0 -> 1)
0到2: 8 (路径: 0 -> 1 -> 2)
0到3: 9 (路径: 0 -> 1 -> 2 -> 3)

1到0: 不可达
1到1: 0
1到2: 3 (路径: 1 -> 2)
1到3: 4 (路径: 1 -> 2 -> 3)

2到0: 不可达
2到1: 不可达
2到2: 0
2到3: 1 (路径: 2 -> 3)

3到0: 不可达
3到1: 不可达
3到2: 不可达
3到3: 0

四、Dijkstra vs Floyd

五、负权边问题

5.1 Dijkstra为什么不能处理负权

Dijkstra的贪心假设：已选中的顶点最短路径不会再被更新。负权边可能使已选中的顶点路径变短，破坏贪心性质。

text

示例：
0 → 1 (1)
0 → 2 (3)
1 → 2 (-2)

Dijkstra从0开始：
选1（dist=1），标记1为已处理
但实际0→2的最短路径是0→1→2（1+(-2)=-1）
此时2已经被标记为dist=3，无法更新

5.2 Floyd处理负权边

Floyd可以处理负权边，但不能有负环（绕一圈总权值为负）。有负环时最短路径为-∞。

c

// 检测负环
for (int i = 0; i < n; i++) {
if (dist[i][i] < 0) {
printf("图中存在负环\\n");
break;
}
}

六、路径还原

两种算法都可以记录路径：

Dijkstra：用prev[]数组，每次更新时记录前驱。

Floyd：用next[][]数组，next[i][j]表示i到j路径中i的下一个顶点。

c

// 打印路径函数
void printPath(int next[MAX_VERTICES][MAX_VERTICES], int i, int j) {
if (next[i][j] == -1) {
printf("无路径");
return;
}
printf("%d", i);
while (i != j) {
i = next[i][j];
printf(" -> %d", i);
}
}

七、算法选择建议

八、小结

这一篇我们学习了最短路径的两种经典算法：

关键代码模板：

c

// Dijkstra核心
while (还有未处理顶点) {
选dist最小的u;
visited[u] = 1;
for (v : u的邻接点) {
if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
}
}

// Floyd核心
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];

下一篇我们讲拓扑排序与关键路径。

九、思考题

欢迎在评论区讨论你的答案。