C语言数据结构系列最短路径篇C语言数据结构系列十六最短路径——Dijkstra与Floyd一、前言二、Dijkstra算法2.1 思想2.2 图解2.3 代码实现三、Floyd算法3.1 思想3.2 代码实现四、Dijkstra vs Floyd五、应用六、下篇预告C语言数据结构系列十六最短路径——Dijkstra与Floyd本篇目标掌握Dijkstra单源最短路和Floyd多源最短路算法摘要本文讲解图论中最短路径的两大经典算法——Dijkstra单源最短路贪心思想O(V²)与Floyd全源最短路动态规划O(V³)。通过图解、C 语言代码实现与对比表格帮助读者理解算法原理、适用场景及局限两者均不能处理负权边并给出导航、路由、游戏寻路等典型应用。一、前言哈喽小伙伴们今天我们来学习最短路径——导航软件的核心算法️Dijkstra从一个点到其他所有点的最短路Floyd任意两点之间的最短路二、Dijkstra算法2.1 思想贪心每次选择距离最近的未访问顶点2.2 图解4231A:0B:∞C:∞D:∞2.3 代码实现#defineINF99999voiddijkstra(intgraph[][MAX],intn,intstart){intdist[MAX];bool visited[MAX]{false};intprev[MAX];for(inti0;in;i){dist[i]graph[start][i];prev[i](dist[i]INFi!start)?start:-1;}dist[start]0;visited[start]true;for(intcount1;countn;count){intu-1;for(intv0;vn;v){if(!visited[v](u-1||dist[v]dist[u])){uv;}}if(u-1||dist[u]INF)break;visited[u]true;for(intv0;vn;v){if(!visited[v]dist[u]graph[u][v]dist[v]){dist[v]dist[u]graph[u][v];prev[v]u;}}}printf(从%c出发的最短距离:\n,startA);for(inti0;in;i){printf(到%c: %d\n,iA,dist[i]);}}三、Floyd算法3.1 思想动态规划三重循环逐步更新最短路径3.2 代码实现voidfloyd(intgraph[][MAX],intn){intdist[MAX][MAX];// 初始化for(inti0;in;i){for(intj0;jn;j){dist[i][j]graph[i][j];}}// 三重循环for(intk0;kn;k){for(inti0;in;i){for(intj0;jn;j){if(dist[i][k]dist[k][j]dist[i][j]){dist[i][j]dist[i][k]dist[k][j];}}}}printf(任意两点最短距离:\n);for(inti0;in;i){for(intj0;jn;j){printf(%d ,dist[i][j]);}printf(\n);}}四、Dijkstra vs Floyd特性DijkstraFloyd时间O(V²)O(V³)用途单源最短路全源最短路负权边❌❌空间O(V)O(V²)五、应用导航软件️网络路由游戏AI寻路六、下篇预告下一篇我们将学习拓扑排序与关键路径 Dijkstra不能处理负权边