一、最短路径问题概述1.1 问题定义给定带权图找出两个顶点之间权值之和最小的路径。分类单源最短路径一个起点到其他所有点的最短路径多源最短路径任意两点之间的最短路径1.2 应用场景场景说明导航系统从A地到B地的最短路线网络路由数据包传输的最优路径社交网络两个人之间的最短关系链游戏开发AI寻路二、Dijkstra算法2.1 算法思想Dijkstra算法是贪心算法从起点开始每次选择距离起点最近且未处理的顶点然后松弛它的邻接边。限制不能处理负权边因为贪心假设已找到最短路径不再更新。步骤初始化dist[start]0其他dist∞选择未处理中dist最小的顶点u标记u为已处理对u的每个邻接点v若dist[u]w(u,v) dist[v]更新dist[v]重复2-4直到所有顶点被处理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} 选2dist1松弛 dist[3]134 visited: {0,2} 选1dist2松弛 dist[3]min(4, 25)4, dist[4]2?无直接边 visited: {0,2,1} 选3dist4松弛 dist[4]426 visited: {0,2,1,3} 选4dist6无松弛 完成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])步骤初始化dist[i][j] 直接边的权值无直接边则为∞ij为0对每个顶点k作为中间点尝试更新所有i,j最终dist[i][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对比项DijkstraFloyd解决问题单源最短路径多源最短路径核心思想贪心动态规划时间复杂度O(V²) / O(E log V)O(V³)空间复杂度O(V)O(V²)负权边不能处理可以处理不能有负环负环检测不能可以检测dist[i][i] 0代码复杂度中等简单三重循环适用场景单起点无负权顶点少需全部距离五、负权边问题5.1 Dijkstra为什么不能处理负权Dijkstra的贪心假设已选中的顶点最短路径不会再被更新。负权边可能使已选中的顶点路径变短破坏贪心性质。text示例 0 → 1 (1) 0 → 2 (3) 1 → 2 (-2) Dijkstra从0开始 选1dist1标记1为已处理 但实际0→2的最短路径是0→1→21(-2)-1 此时2已经被标记为dist3无法更新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); } }七、算法选择建议场景推荐理由单源、无负权、稠密图Dijkstra(邻接矩阵)O(V²)简单实现单源、无负权、稀疏图Dijkstra(堆优化)O(E log V)高效单源、有负权无负环Bellman-Ford可处理负权多源、顶点少V≤500Floyd代码简单O(V³)可接受多源、顶点多多次Dijkstra每点跑一次需要检测负环Floyd / Bellman-Ford可检测八、小结这一篇我们学习了最短路径的两种经典算法算法核心时间复杂度适用场景Dijkstra贪心 松弛O(V²) / O(E log V)单源、无负权Floyd动态规划O(V³)多源、顶点少关键代码模板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];下一篇我们讲拓扑排序与关键路径。九、思考题Dijkstra算法中为什么不能处理负权边能举出一个反例吗Floyd算法的三重循环中为什么k必须在最外层如果把k放在内层会怎样如何用Dijkstra算法找出从起点到终点的具体路径不只是距离如果图中存在负环Floyd算法的结果会怎样如何检测欢迎在评论区讨论你的答案。