C语言迪杰斯特拉算法求最短路径详解

<>准备一张地图

盗取了一个不知名朋友的图，嘻嘻。

<>算法举例描述

目的：在一张地图中找出地点A和地点B的一条最短路径（实际上该算法每次运算会求出地点A到其他各个地点的各一条最短路径）。
过程：
1）以从1号地点到4号地点为例。
2）标记1号地点。（标记的作用将在后面得到体会，当全部地点都被标记完时，最短路径就求出来了！），此时在草稿本上画出（99为不可直达）
线路 距离总和 1->2 2 1->3 5 1->4 99 1->5 99 1->6 99 1->7 99

3）通过比较我们可以得到1->2这段距离是最短的，那么此时我们标记2号地点表示已经找到了1号到2号的最短距离。那么这时候我们从1号到2号以外地点的距离是否能减短，比较1->3和1–>2->3可知1->2->3距离为4，更短一些，修改1号到3号的线路和距离，再依次比较剩下未标记的地点线路。然后修改草稿
线路 距离总和 1->2 2 1->2->3 4 1->2->4 6 1->2->5 8 1->6 99 1->7 99

4）通过比较我们可以得到未标记的地点中1到3号的距离最短，可知1到3号的最短路径也已经得出结论。那么标记3号，此时1号到未标记的地点的距离是原来的路线近一些呢，还是先去3号，在从3号去更近呢，比较一下。拿4号为例，上一次结论中1->2->4=6，此时1->2->3->4=5,更短一些，修改该路线；然后依次比较1到5号，1到6号，1到7号的最短距离并修改可以更短的。
线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->6 7 1->7 99
5）根据以上规律此时标记4号，比较并修改可以得到更短距离的5、6、7号地点
线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->4->6 6 1->2->3->4->7 9
6）根据以上规律此时标记6号，比较并修改可以得到更短距离的5、7号地点
线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->4->6 6 1->2->3->4->6->
7 8
7）根据以上规律此时标记5号（两距离一样，随意选一个），比较并修改可以得到更短距离的7号地点
线路 距离总和 1->2 2 1->2->3 4 1->2->3->4 5 1->2->5 8 1->2->3->4->6 6 1->2->3->4->6->
7 8
8）标记7号地点，此时已经没有未标记的地点，表示所有地点均已经找到了从1号到它的最短路径！算法结束。

<>算法总结

求A到B的最短路径
1、在地点集合Map中，先标记A。

2、存储A直接到其他各地点的路径和距离，选择最短的一条，假设为A->C，那此时标记C，表示已经找到A到C的最短路径，比较一下A->其他的距离和A->C->其他的距离，如果经过C的路线比较短，修改A->其他为A->C->其他，并及时更新其目前最短距离。
3、重复执行第2步直到所有地点均被标记。
4、输出结果中的A->…->B路径和距离（…表示0到多个中间点）。

<>代码实现

用一个地图结构保存该地图
//最大地点数 #define MAXCOUNT 20 //不可能距离值（两地点无直接线路时） #define MAXDISTANCE 99 //地图结构
typedef struct map { //地点数量 int nodeCount; //地点标识 int id[MAXCOUNT]; //各地点间距离
distance[i][j]=distance[j][i]，表示i地点和j地点的距离 int distance[MAXCOUNT][MAXCOUNT]; }
Map;
由于该地图线路较多，这里采用文件读入方式，编写map.txt，格式为
地点数n1
线路数n2
n2个（地点a的id 地点b的id a到b的距离 ）
7 12 1 2 2 1 3 5 2 3 2 2 5 6 2 4 4 4 3 1 3 6 3 4 5 4 4 6 1 4 7 4 5 7 1 6 7 2
编写文件读入地图函数
//读取map.txt中的信息 void readMap(Map *map) { //以读形式打开文件 FILE *fp=fopen("map.txt",
"r"); //读取地点数量 fscanf(fp,"%d",&map->nodeCount); int n; //读取路线数量 fscanf(fp,"%d",&
n); int i,j; //初始化地点id for(i=1;i<=map->nodeCount;i++) { map->id[i]=i; }
//初始化每两地点均无路线 for(i=1;i<MAXCOUNT;i++) { for(j=1;j<MAXCOUNT;j++) { map->distance[
i][j]=MAXDISTANCE; } } //读入线路 int k,d; for(k=1;k<=n;k++) { fscanf(fp,"%d%d%d",&i
,&j,&d); map->distance[i][j]=d; map->distance[j][i]=d; } //关闭文件 fclose(fp); }
编写打印地图函数
//打印地图信息 void displayMap(Map map) { int i,j; printf("地点个数:%d\n",map.nodeCount);
printf("各地点间距离（...表示无路线）:\n"); printf(" "); for(i=1;i<=map.nodeCount;i++) {
printf("%-3d ",i); } printf("\n"); for(i=1;i<=map.nodeCount;i++) { printf("%-3d
",i); for(j=i;j<=map.nodeCount;j++) { if(map.distance[i][j]==MAXDISTANCE) {
printf("... "); } else { printf("%-3d ",map.distance[i][j]); } } printf("\n"); }
printf("\n"); }
编写路径结构
//路线结构 typedef struct road { //经过地点id int path[MAXCOUNT]; //距离 int minDistance;
//经过的地点数 int count; }Road;
迪杰斯特拉算法实现求地点a到其他地点的最短路径
//迪杰斯特拉算法求地点a到其他地点的最短路径 Road *djstl(Map map,int id_a) { //所有路线 Road r[
MAXCOUNT]; //标记数组（0为未标记，1为已标记） int flag[MAXCOUNT]={0}; int i; //初始化所有路线 for(i=1;
i<=map.nodeCount;i++) { /*a地点到其他各个地点的距离*/ /*起点是a，终点是i*/ r[i].count=2; r[i].path[
0]=id_a; r[i].path[1]=i; r[i].minDistance=map.distance[id_a][i]; } //标记a flag[
id_a]=1; //还有未标记地点则循环执行 while(1) { //寻找a到未标记的地点的最短路线的下标 int index=-1; for(i=1;i
<=map.nodeCount;i++) { //未标记 if(flag[i]==0) { if(index==-1) { index=i; } else if
(r[i].minDistance<r[index].minDistance) { index=i; } } } //不存在未标记下标了 if(index==-
1) { return r; } //标记index flag[index]=1; //比较并修改其他路线此时的最短路径 for(i=1;i<=map.
nodeCount;i++) { //未找到最短路径的地点 if(flag[i]==0) {
//a->...->i短还是a->...->index->i短，后者短，则说明a到i有更好的选择 if(r[i].minDistance>r[index].
minDistance+map.distance[index][i]) { /*将r[index]的值赋予r[i]，并修改r[i]的最短路径*/ r[i].
count=r[index].count+1; int j; for(j=0;j<r[i].count-1;j++) { r[i].path[j]=r[
index].path[j]; } r[i].path[j]=i; r[i].minDistance=r[index].minDistance+map.
distance[index][i]; } } } } }
输出已求路径
//打印a到b的最短路径 void displayRoad(Road rab) { printf("距离:%d\n",rab.minDistance);
int i; printf("路线:"); for(i=0;i<rab.count-1;i++) { printf("%d-->",rab.path[i]);
} printf("%d\n\n",rab.path[i]); }
编写主函数测试
int main() { //地图变量 Map map; //读取地图 readMap(&map); //打印地图信息 displayMap(map);
int id_a,id_b; printf("id_a:"); scanf("%d",&id_a); printf("id_b:"); scanf("%d",&
id_b); printf("搜索最短路径中，请稍后...\n"); Road *r=djstl(map,id_a); printf("搜索最短路径完毕！\n"
); displayRoad(r[id_b]); return 0; }
测试1号到4号地点的最短路径

测试1到7号地点的最短距离

结果和以上所算一致，实现完毕！

• « 上一篇：魔改YOLOv5算法系列（1）——注意力机制添加
• » 下一篇：React学习（状态数据更新）