更改域名代理商对网站有影响吗,新龙华网站建设,确认已有81人感染,手机网站关键本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文#xff1a;
图论#xff1a;Dijkstra算法——最详细的分析#xff0c;图文并茂#xff0c;一次看懂#xff01;-CSDN博客 以下附上…本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文
图论Dijkstra算法——最详细的分析图文并茂一次看懂-CSDN博客 以下附上实现代码
#include stdio.h
#include stdlib.h
#include string.h
#define MaxE 5
#define MVNum 100
#define MaxInt 32767
typedef struct{char vex[MVNum]; //顶点表int arcs[MVNum][MVNum];//邻接矩阵权重为整数int Vexnum;//顶点数int arcnum; //边数
}AMGraph;
//全局变量部分
int cunt0; //为存储矩阵计数
int store[MaxE][MVNum]; //存储结果矩阵 ,每个结果数组的第一位位存最短路径值后面为路径节点
int ismin[MVNum]; //记录该几点是否已为最小值
//函数定义部分
void Dijsktra(AMGraph *a,char s,char e);
void Init(AMGraph *a);
int Read(AMGraph *a);
void Cal(AMGraph *a);
void show(int a[]);
int getIndex(AMGraph *a,char c);
//函数部分
void Init(AMGraph *a){ //初始化图和存储数组 a-arcnum0;a-Vexnum0;for(int i0;iMVNum;i){for(int j0;jMVNum;j){a-arcs[i][j]MaxInt;}}for(int i0;iMVNum;i){a-vex[i] 0;store[cunt][i] 0;ismin[i] 0;}
}
int getIndex(AMGraph *a,char c){ //获取节点在图中的位置 int rs;for(int i0;ia-Vexnum;i){if(ca-vex[i])return i;}
}
void show(int a[]){ //输出数据 printf(\n[RES]:\n);printf(最短距离:%d\n,a[0]); //第一位为数字直接输出 printf(最短路径:%c,a[1]);for(int i2;iMVNum;i){ //后面皆为字符; if(a[i] 0){break;}printf(-%c,a[i]);}
}
void Dijsktra(AMGraph *a,char s,char e){int min0;//记录每一趟的最小值以及该节点 char minv;int *lgti (int*)malloc(sizeof(int)*a-Vexnum); //该数组用于更新节点节点的最短路径char ** lgtc (char**)malloc(sizeof(char*)*a-Vexnum); //该数组用于保存每个节点当前最短路径for(int i0;ia-Vexnum;i){ //初始化 lgtc[i](char*)malloc(sizeof(char)*a-Vexnum);lgtc[i][0] s;for(int j1;ja-Vexnum;j)lgtc[i][j]0;lgti[i] MaxInt;}minvs;for(int i0;ia-Vexnum-1;i){ //每次确定一个最小路径最多共需v-1趟完成for(int j0;ja-Vexnum;j){ //每趟对v个节点路径进行更新 //printf(\n%c:new %d,old %d\n,a-vex[j],mina-arcs[getIndex(a,minv)][j],lgti[j]);if(mina-arcs[getIndex(a,minv)][j]lgti[j]){ //若更新节点值小于现有最小值则更新为改值 lgti[j] mina-arcs[getIndex(a,minv)][j];strcpy(lgtc[j],lgtc[getIndex(a,minv)]);lgtc[j][strlen(lgtc[j])] a-vex[j]; }}min MaxInt;printf([TRV %d]:,cunt1); for(int j0;ja-Vexnum;j){if(lgti[j]minismin[j]0){ //若小于min且未定为最小值则记录 min lgti[j];minv a-vex[j];}}printf(新增最小路径: %c\n,minv);if(minve){printf(Success!\n);store[cunt][0] min;for(int i0;istrlen(lgtc[getIndex(a,e)]);i){store[cunt][i1](int)lgtc[getIndex(a,e)][i];}cunt;break; }ismin[getIndex(a,minv)]1;}
}
void Cal(AMGraph *a){ //计算结果Dijsktrachar start,end;getchar(); //结果存储 printf(请输入起始节点: );scanf( %c %c,start,end);Dijsktra(a,start,end);
}
int Read(AMGraph *a){ //读取数据 int n,m,lgt;char ca,cb; printf(请输入n,m:); scanf(%d%d,n,m);if(n0m0)return 1;a-Vexnum n;a-arcnum m;printf(请输入顶点:);for(int i0;in;i){scanf( %c,a-vex[i]); //储存节点 }getchar(); printf(请输入边 \n);for(int i0;im;i){ //存储边 scanf( %c %c %d,ca,cb,lgt);a-arcs[getIndex(a,ca)][getIndex(a,cb)]lgt;}return 0;
}int main(){int flag0; //记录是否输入停止 AMGraph *a (AMGraph*)malloc(sizeof(AMGraph));printf(多组数据每组数据有 m3 行。\n第一行为两个整数 n 和 m分别代表城市个数 n 和路径条数 m。\n第二行有 n 个字符代表每个城市的名字。\n第三行到第m2 行每行有两个字符 a 和 b 和一个整数 d代表从城市 a 到城市 b 有一条距离为 d 的路。\n最后一行为两个字符代表待求最短路径的城市起点和终点。\n当 n 和m 都等于 0 时输入结束);while(1){Init(a); //初始化图 printf(\n | -FZC- | \n\n);flag Read(a); //读取信息if(flag1){printf(\n | -FZC- | \n\n);printf(\nFOLLOWING OUTPUI:\n);printf(共寻径[%d]次\n,cunt);for(int i0;icunt;i)show(store[i]);break; }Cal(a); //计算距离并存储结果 }return 0;
}
以上代码仅供参考欢迎交流。
