图的最短路径：从单源到多源，一次讲透
最短路径问题，说白了就是「怎么走最近」。你想想看，地图导航、网络路由、社交关系链……背后都离不开这个算法。今天我们就来啃下这块硬骨头——迪杰斯特拉和弗洛伊德，两个经典算法，一个管单源，一个管多源。
我个人习惯把这两个算法放在一起讲，因为它们正好互补。迪杰斯特拉像是个「专注的工匠」，一次只解决一个起点到所有点的最短路径；弗洛伊德则像个「全局规划师」，一口气算出所有点对之间的最短距离。嗯，咱们一个一个来。
核心要点：
- 迪杰斯特拉算法：单源最短路径，不能处理负权边
- 弗洛伊德算法：多源最短路径，可以处理负权边（但不能有负权环）
- 路径记录：两种算法都需要记录前驱节点，才能输出完整路径
迪杰斯特拉算法：单源最短路径的经典解法
我在项目中第一次用迪杰斯特拉，是做一个嵌入式导航系统。当时芯片资源有限，内存只有几十KB，我不得不手写一个最小堆来优化。嗯，那段经历让我对这个算法有了刻骨铭心的理解。
算法的核心思想其实很简单：每次从「未确定最短路径」的节点中，选一个距离起点最近的，然后用它去更新邻居的距离。说白了就是「贪心」——我每次都选当前看起来最优的，最终全局最优。
我的小技巧：写迪杰斯特拉时，我习惯用三个数组：dist[] 存距离、visited[] 标记已确定、prev[] 记录前驱。这样代码结构清晰，不容易出错。
代码实现（邻接矩阵版）
#define INF 0x3F3F3F3F
#define MAXV 100
// 迪杰斯特拉算法
void dijkstra(int graph[MAXV][MAXV], int n, int start) {
int dist[MAXV]; // 最短距离
int visited[MAXV]; // 是否已确定
int prev[MAXV]; // 前驱节点
// 初始化
for (int i = 0; i < n; i++) {
dist[i] = graph[start][i];
visited[i] = 0;
prev[i] = (dist[i] != INF && i != start) ? start : -1;
}
visited[start] = 1;
dist[start] = 0;
// 主循环：每次确定一个节点
for (int count = 1; count < n; count++) {
// 找未访问中距离最小的
int minDist = INF;
int u = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
u = i;
}
}
if (u == -1) break; // 剩下的不可达
visited[u] = 1;
// 更新邻居
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != INF) {
int newDist = dist[u] + graph[u][v];
if (newDist < dist[v]) {
dist[v] = newDist;
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]);
printPath(prev, start, i);
printf("\n");
}
}
}我曾经踩过的坑：有一次我忘了初始化 prev 数组，结果路径输出时出现了死循环。后来我养成了习惯——每次初始化 dist 时，顺手把 prev 也初始化了。如果 dist[i] 不是 INF 且 i 不是起点，prev[i] 就设为起点，否则设为 -1。
弗洛伊德算法：多源最短路径的优雅解法
弗洛伊德算法就更有意思了。它用动态规划的思想，代码极其简洁——三层循环，搞定所有点对的最短路径。我第一次看到这个算法时，心里想的是：「就这？这么简单？」但仔细一琢磨，才发现它的精妙之处。
核心思想：逐步允许使用更多的中间节点。一开始只允许用节点0作为中间节点，然后允许用节点0和1，直到所有节点都可以作为中间节点。每次引入一个新节点，就检查它能不能让路径变短。
代码实现
#define INF 0x3F3F3F3F
#define MAXV 100
// 弗洛伊德算法
void floyd(int graph[MAXV][MAXV], int n) {
int dist[MAXV][MAXV]; // 距离矩阵
int next[MAXV][MAXV]; // 路径记录矩阵
// 初始化
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;
}
}
}
// 核心：三层循环
for (int k = 0; k < n; k++) { // 中间节点
for (int i = 0; i < n; i++) { // 起点
if (dist[i][k] == INF) continue;
for (int j = 0; j < n; j++) { // 终点
if (dist[k][j] == INF) continue;
int newDist = dist[i][k] + dist[k][j];
if (newDist < dist[i][j]) {
dist[i][j] = newDist;
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 && dist[i][j] != INF) {
printf("%d -> %d: 距离=%d, 路径=", i, j, dist[i][j]);
printPathFloyd(next, i, j);
printf("\n");
}
}
}
}为什么弗洛伊德能处理负权边？因为它不是贪心，而是动态规划。它遍历了所有可能的中间节点组合，所以即使有负权边，只要没有负权环，就能找到正确的最短路径。但如果有负权环……嗯，那就会无限循环地变小，算法检测不到，需要额外处理。
路径记录与输出：让结果看得见
光算出距离还不够，你得告诉用户「怎么走」。路径记录是这两个算法中容易被忽略的部分，但实际项目中，路径往往比距离更重要。
我个人的做法是：迪杰斯特拉用 prev[] 数组，弗洛伊德用 next[][] 矩阵。输出时统一用递归回溯。
路径输出函数
// 迪杰斯特拉的路径输出（递归回溯）
void printPath(int prev[], int start, int end) {
if (start == end) {
printf("%d", start);
return;
}
if (prev[end] == -1) {
printf("无路径");
return;
}
printPath(prev, start, prev[end]);
printf(" -> %d", end);
}
// 弗洛伊德的路径输出（利用 next 矩阵）
void printPathFloyd(int next[MAXV][MAXV], int start, int end) {
if (next[start][end] == -1) {
printf("无路径");
return;
}
printf("%d", start);
while (start != end) {
start = next[start][end];
printf(" -> %d", start);
}
}避坑指南：我曾经在路径输出时犯过一个低级错误——递归函数里忘了处理起点等于终点的情况，结果栈溢出了。所以写递归时，一定要先写终止条件。
两种算法的对比与选择
| 对比维度 | 迪杰斯特拉 | 弗洛伊德 |
|---|---|---|
| 适用场景 | 单源最短路径（一个起点到所有点） | 多源最短路径（所有点对之间） |
| 时间复杂度 | O(V²) 或 O(E log V)（堆优化） | O(V³) |
| 空间复杂度 | O(V) | O(V²) |
| 负权边 | 不支持 | 支持（无负权环） |
| 实现复杂度 | 中等（需要选最小节点） | 简单（三层循环） |
| 路径记录 | 一维 prev[] 数组 | 二维 next[][] 矩阵 |
你想想看，如果只需要知道从你家到全城所有地方的最短路径，用迪杰斯特拉就够了。但如果你要做一个「全国城市间最短路径查询系统」，用户可能问任意两个城市之间的距离，那弗洛伊德一次算完，后面直接查表，效率更高。
重要提醒：弗洛伊德虽然代码简单，但 O(V³) 的时间复杂度意味着当节点数超过 500 时，运行时间就会变得可观。我在一个项目中处理 1000 个节点的图，弗洛伊德跑了将近 10 秒……后来换成了对每个节点跑一次堆优化的迪杰斯特拉，反而更快。所以，选算法不能只看代码简洁，还要看数据规模。
好了，关于最短路径的两个经典算法，我们就聊到这里。代码我已经给了，关键点也点到了。剩下的就是你自己动手去写、去调试、去踩坑——嗯，踩坑也是一种学习，我当年就是这么过来的。
公众号：蓝海资料掘金营，微信 deep3321