_DataStructure_C_Impl:Dijkstra算法求最短路径
算法 路径 Dijkstra impl
2023-09-11 14:20:43 时间
// _DataStructure_C_Impl:Dijkstra #include<stdio.h> #include<stdlib.h> #include<string.h> typedef char VertexType[4]; typedef char InfoPtr; typedef int VRType; #define INFINITY 100000 //定义一个无限大的值 #define MaxSize 50 //最大顶点个数 typedef int PathMatrix[MaxSize][MaxSize]; //定义一个保存最短路径的二维数组 typedef int ShortPathLength[MaxSize]; //定义一个保存从顶点v0到顶点v的最短距离的数组 typedef enum{DG,DN,UG,UN}GraphKind; typedef struct{ VRType adj; //对于无权图,用1表示相邻,0表示不相邻;对于带权图,存储权值 InfoPtr *info; //与弧或边的相关信息 }ArcNode,AdjMatrix[MaxSize][MaxSize]; //图的类型定义 typedef struct{ VertexType vex[MaxSize]; //用于存储顶点 AdjMatrix arc; //邻接矩阵,存储边或弧的信息 int vexnum,arcnum; //顶点数和边(弧)的数目 GraphKind kind; //图的类型 }MGraph; //加入一个存储网的行、列和权值的类型定义 typedef struct{ int row; int col; int weight; }GNode; //採用邻接矩阵表示法创建有向网N void CreateGraph(MGraph *N,GNode *value,int vnum,int arcnum,VertexType *ch){ int i,j,k,w; char s[MaxSize]; VertexType v1,v2; N->vexnum=vnum; N->arcnum=arcnum; for(i=0;i<vnum;i++) strcpy(N->vex[i],ch[i]); //初始化邻接矩阵 for(i=0;i<N->vexnum;i++) for(j=0;j<N->vexnum;j++){ N->arc[i][j].adj=INFINITY; N->arc[i][j].info=NULL; //弧的信息初始化为空 } for(k=0;k<arcnum;k++){ i=value[k].row; j=value[k].col; N->arc[i][j].adj=value[k].weight; } N->kind=DN; //图的类型为有向网 } //输出邻接矩阵存储表示的图N void DisplayGraph(MGraph N){ int i,j; printf("有向网具有%d个顶点%d条弧。顶点依次是: ",N.vexnum,N.arcnum); for(i=0;i<N.vexnum;++i) //输出网的顶点 printf("%s ",N.vex[i]); printf("\n有向网N的:\n"); //输出网N的弧 printf("序号i="); for(i=0;i<N.vexnum;i++) printf("%8d",i); printf("\n"); for(i=0;i<N.vexnum;i++) { printf("%8d",i); for(j=0;j<N.vexnum;j++) printf("%8d",N.arc[i][j].adj); printf("\n"); } } /*用Dijkstra算法求有向网N的v0顶点到其余各顶点v的最短路径P[v]及带权长度D[v]*/ /*final[v]为1表示v∈S,即已经求出从v0到v的最短路径*/ void Dijkstra(MGraph N,int v0,PathMatrix path,ShortPathLength dist){ int v,w,i,k,min; int final[MaxSize]; //记录v0到该顶点的最短路径是否已求出 for(v=0;v<N.vexnum;v++){ //数组dist存储v0到v的最短距离,初始化为v0到v的弧的距离 final[v]=0; dist[v]=N.arc[v0][v].adj; for(w=0;w<N.vexnum;w++) path[v][w]=0; if(dist[v]<INFINITY){ //假设从v0到v有直接路径。则初始化路径数组 path[v][v0]=1; path[v][v]=1; } } dist[v0]=0; //v0到v0的路径为0 final[v0]=1;//v0顶点并入集合S /*从v0到其余G.vexnum-1个顶点的最短路径,并将该顶点并入集合S*/ for(i=1;i<N.vexnum;i++){ min=INFINITY; for(w=0;w<N.vexnum;w++) if(!final[w]&&dist[w]<min){ //在不属于集合S的顶点中找到离v0近期的顶点 v=w; //将其离v0近期的顶点w赋给v,其距离赋给min min=dist[w]; } final[v]=1; //将v并入集合S for(w=0;w<N.vexnum;w++) //利用新并入集合S的顶点。更新v0到不属于集合S的顶点的最短路径长度和最短路径数组 if(!final[w]&&min<INFINITY&&N.arc[v][w].adj<INFINITY&&(min+N.arc[v][w].adj<dist[w])){ dist[w]=min+N.arc[v][w].adj; for(k=0;k<N.vexnum;k++) path[w][k]=path[v][k]; path[w][w]=1; } } } void main(){ int i,j,vnum=6,arcnum=9; MGraph N; GNode value[]={{0,1,30},{0,2,60},{0,4,150},{0,5,40}, {1,2,40},{1,3,100},{2,3,50},{3,4,30},{4,5,10}}; VertexType ch[]={"v0","v1","v2","v3","v4","v5"}; PathMatrix path; /*用二维数组存放最短路径所经过的顶点*/ ShortPathLength dist; /*用一维数组存放最短路径长度*/ CreateGraph(&N,value,vnum,arcnum,ch); /*创建有向网N*/ DisplayGraph(N); /*输出有向网N*/ Dijkstra(N,0,path,dist); printf("%s到各顶点的最短路径长度为:\n",N.vex[0]); for(i=0;i<N.vexnum;++i) if(i!=0) printf("%s-%s:%d\n",N.vex[0],N.vex[i],dist[i]); system("pause"); }
相关文章
- java实现Kruskal算法
- Java实现 蓝桥杯VIP 算法训练 整除问题
- 最短路径—Dijkstra算法和Floyd算法
- (算法)字符串的组合
- 算法练习之二叉树的最小深度,路径总和
- 数据结构与算法-2 最短路径 Dijkstra A*搜索 [MD]
- 初探Prisma背后的算法
- 程序员的算法趣题Q18: 水果酥饼日
- Interview:算法岗位面试—10.17早上—上海某科技公司算法岗位(偏算法,独角兽)非技术面试之比赛项目讲解和项目意义的探讨
- DL之CNN:利用卷积神经网络算法(2→2,基于Keras的API-Sequential)利用MNIST(手写数字图片识别)数据集实现多分类预测
- 基于Dijkstra和A*算法的机器人路径规划(Matlab代码实现)
- 基于蚁群算法的时延Petri网(ACOTPN)路径规划算法(Matlab代码实现)
- 【路径规划】基于D*算法的移动机器人路径规划(Matlab代码实现)
- 基于蚁群算法的二维路径规划matlab仿真
- 关于经过若干指定节点最短路径问题的算法。
- 设计一个算法,输出从u到v的全部最短路径(採用邻接表存储)
- 神经网络和反向传播算法——反向传播算法本质上是随机梯度下降,链式求导法则而来的
- 最短路径 | 深入浅出Dijkstra算法(一)
- 基于Astar算法的智能避障最短路径搜索matlab仿真,可以任意选择起点和终点
- 基于Astar算法的栅格地图最优路径搜索matlab仿真,可以修改任意数量栅格
- 机器人C++库(12) Robotics Library 之路径规划算法:PRM、RRT、EET算法
- (1)Python-OpenCV视频帧间差分、高斯混合建模、背景差分提取前景目标轮廓、KCF目标跟踪、Meanshift算法跟踪
- C++算法之字符串
- 数据结构和算法 十八、图的结构、最短路径、广度优先搜索、深度优先搜索