数据结构进阶（五）：最短路径——Dijkstra 与 Floyd 算法

引言

上一篇我们学习了图的基本概念、存储方式和两种遍历算法（DFS 与 BFS）。BFS 能解决无权图的最短路径问题——因为每条边权值相等，先搜到的就是最短的。

但现实中，路有长短、网有快慢——这就是带权图。从北京到上海走哪条高速最快？路由器选哪条链路延迟最小？这些都需要最短路径算法。

本文将讲解两种最经典的最短路径算法：Dijkstra（单源最短路径）和Floyd（多源最短路径）。

第一部分：Dijkstra 算法（单源最短路径）

一、算法思想

Dijkstra 算法用于求一个源点到其他所有顶点的最短路径，要求所有边的权值 ≥ 0（不能处理负权边）。

核心思想：贪心。每次从"未确定最短路径的顶点"中选出距离起点最近的一个，确定为最短，然后用它去更新它的邻居。

二、算法过程图解

三、Dijkstra 代码实现

#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <stdbool.h> #define MAX_V 100 #define INF INT_MAX typedef struct { int vertexNum; int edgeNum; int matrix[MAX_V][MAX_V]; // 邻接矩阵存储边权 } Graph; // 初始化图 void initGraph(Graph* g, int n) { g->vertexNum = n; g->edgeNum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g->matrix[i][j] = (i == j) ? 0 : INF; // 自己到自己是 0，其余 INF } } } // 添加边 void addEdge(Graph* g, int u, int v, int w) { g->matrix[u][v] = w; g->matrix[v][u] = w; // 无向图 g->edgeNum++; } // 在未确定顶点中找距离最小的 int findMinDist(int dist[], bool visited[], int n) { int min = INF; int minIndex = -1; for (int i = 0; i < n; i++) { if (!visited[i] && dist[i] < min) { min = dist[i]; minIndex = i; } } return minIndex; } // Dijkstra 算法 void dijkstra(Graph* g, int start) { int dist[MAX_V]; // dist[i] = start 到 i 的最短距离 int prev[MAX_V]; // prev[i] = i 的前驱顶点 bool visited[MAX_V]; // visited[i] = i 是否已确定 // 初始化 for (int i = 0; i < g->vertexNum; i++) { dist[i] = INF; prev[i] = -1; visited[i] = false; } dist[start] = 0; // 循环 n 次 for (int count = 0; count < g->vertexNum; count++) { // ① 选距离最小的未确定顶点 int u = findMinDist(dist, visited, g->vertexNum); if (u == -1) break; // 剩下的都不可达 visited[u] = true; // ② 标记为已确定 // ③ 用 u 更新邻居 for (int v = 0; v < g->vertexNum; v++) { if (!visited[v] && g->matrix[u][v] != INF) { int newDist = dist[u] + g->matrix[u][v]; if (newDist < dist[v]) { dist[v] = newDist; prev[v] = u; } } } } // 输出结果 printf("===== Dijkstra 结果（起点 %c）=====\n", 'A' + start); printf("顶点\t最短距离\t前驱\t路径\n"); for (int i = 0; i < g->vertexNum; i++) { printf("%c\t", 'A' + i); if (dist[i] == INF) { printf("∞\t\t-\t不可达\n"); } else { printf("%d\t\t%c\t", dist[i], prev[i] == -1 ? '-' : ('A' + prev[i])); // 输出路径 int path[MAX_V], p = 0, cur = i; while (cur != -1) { path[p++] = cur; cur = prev[cur]; } for (int j = p - 1; j >= 0; j--) { printf("%c", 'A' + path[j]); if (j > 0) printf(" → "); } printf("\n"); } } }

四、为什么 Dijkstra 不能处理负权边

第二部分：Floyd 算法（多源最短路径）

一、算法思想

Dijkstra 只能求一个起点到其他所有点的最短路径。如果要任意两点之间的最短路径（比如地图上任意两个城市之间的最短距离），需要调用 n 次 Dijkstra，复杂度 O(n³)。

Floyd 算法一次性算出所有点对的最短路径，复杂度也是 O(n³)，但常数因子更小，代码极短。

核心思想：动态规划。对每一对顶点 (i, j)，尝试以另一个顶点 k 作为中转站，看是否能让路径更短。

二、算法过程图解

再举一个更明显的例子：

三、Floyd 代码实现

void floyd(Graph* g) { int n = g->vertexNum; int dist[MAX_V][MAX_V]; // dist[i][j] = i 到 j 的最短距离 int path[MAX_V][MAX_V]; // path[i][j] = i 到 j 路径上 j 的前驱 // 初始化 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = g->matrix[i][j]; if (i != j && g->matrix[i][j] != INF) { path[i][j] = i; // i→j 直达，前驱是 i } else { path[i][j] = -1; // 不可达或无前驱 } } } // 三重循环 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) { int newDist = dist[i][k] + dist[k][j]; if (newDist < dist[i][j]) { dist[i][j] = newDist; path[i][j] = path[k][j]; // i→j 的路径 = i→k→j } } } } } // 输出结果 printf("\n===== Floyd 结果 =====\n"); printf("最短距离矩阵：\n"); printf(" "); for (int i = 0; i < n; i++) printf("%4c", 'A' + i); printf("\n"); for (int i = 0; i < n; i++) { printf("%c ", 'A' + i); for (int j = 0; j < n; j++) { if (dist[i][j] == INF) printf(" ∞"); else printf("%4d", dist[i][j]); } printf("\n"); } }

第三部分：Dijkstra vs Floyd

第四部分：完整测试代码

#include <stdio.h> #include <stdlib.h> #include <limits.h> #include <stdbool.h> #define MAX_V 100 #define INF INT_MAX typedef struct { int vertexNum; int edgeNum; int matrix[MAX_V][MAX_V]; } Graph; void initGraph(Graph* g, int n) { g->vertexNum = n; g->edgeNum = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) g->matrix[i][j] = (i == j) ? 0 : INF; } void addEdge(Graph* g, int u, int v, int w) { g->matrix[u][v] = w; g->matrix[v][u] = w; g->edgeNum++; } int findMinDist(int dist[], bool visited[], int n) { int min = INF, minIndex = -1; for (int i = 0; i < n; i++) { if (!visited[i] && dist[i] < min) { min = dist[i]; minIndex = i; } } return minIndex; } void dijkstra(Graph* g, int start) { int dist[MAX_V], prev[MAX_V]; bool visited[MAX_V]; for (int i = 0; i < g->vertexNum; i++) { dist[i] = INF; prev[i] = -1; visited[i] = false; } dist[start] = 0; for (int count = 0; count < g->vertexNum; count++) { int u = findMinDist(dist, visited, g->vertexNum); if (u == -1) break; visited[u] = true; for (int v = 0; v < g->vertexNum; v++) { if (!visited[v] && g->matrix[u][v] != INF) { int newDist = dist[u] + g->matrix[u][v]; if (newDist < dist[v]) { dist[v] = newDist; prev[v] = u; } } } } printf("===== Dijkstra（起点 %c）=====\n", 'A' + start); for (int i = 0; i < g->vertexNum; i++) { printf("%c: ", 'A' + i); if (dist[i] == INF) printf("不可达\n"); else printf("距离=%d, 前驱=%c\n", dist[i], prev[i] == -1 ? '-' : ('A' + prev[i])); } } void floyd(Graph* g) { int n = g->vertexNum; int dist[MAX_V][MAX_V]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dist[i][j] = g->matrix[i][j]; 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) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; printf("\n===== Floyd 最短距离矩阵 =====\n "); for (int i = 0; i < n; i++) printf("%4c", 'A' + i); printf("\n"); for (int i = 0; i < n; i++) { printf("%c ", 'A' + i); for (int j = 0; j < n; j++) { if (dist[i][j] == INF) printf(" ∞"); else printf("%4d", dist[i][j]); } printf("\n"); } } int main() { Graph g; initGraph(&g, 6); addEdge(&g, 0, 1, 5); // A-B: 5 addEdge(&g, 0, 3, 2); // A-D: 2 addEdge(&g, 1, 2, 3); // B-C: 3 addEdge(&g, 1, 4, 1); // B-E: 1 addEdge(&g, 2, 5, 4); // C-F: 4 addEdge(&g, 3, 4, 6); // D-E: 6 addEdge(&g, 4, 5, 2); // E-F: 2 dijkstra(&g, 0); floyd(&g); return 0; }

总结

一、核心对比

二、一句话记忆

Dijkstra 用贪心每次选最近的未确定顶点更新邻居，求单源最短路径 O(n²)。Floyd 用三重循环枚举中转站，一次性求所有点对最短路径 O(n³)。两者都不支持负权边，有负权边需要用 Bellman-Ford。