数据结构进阶（五）：最短路径——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对比项DijkstraFloyd解决问题单源最短路径多源最短路径时间复杂度O(n²)朴素O(n³)空间复杂度O(n)O(n²)负权边❌ 不支持❌ 不支持但可检测实现难度中等极简5 行核心适用场景求一点到其他所有点求所有点对、求图的传递闭包第四部分完整测试代码#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; }总结一、核心对比对比项DijkstraFloyd解决问题一个起点到所有点所有点对思想贪心动态规划时间复杂度O(n²)O(n³)负权边❌❌代码量30 行5 行核心二、一句话记忆Dijkstra 用贪心每次选最近的未确定顶点更新邻居求单源最短路径 O(n²)。Floyd 用三重循环枚举中转站一次性求所有点对最短路径 O(n³)。两者都不支持负权边有负权边需要用 Bellman-Ford。