本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文：
图论：Dijkstra算法——最详细的分析，图文并茂，一次看懂！-CSDN博客
以下附上实现代码：文章来源：https://www.toymoban.com/news/detail-763704.html
#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 cunt=0; //为存储矩阵计数
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->arcnum=0;
a->Vexnum=0;
for(int i=0;i<MVNum;i++){
for(int j=0;j<MVNum;j++){
a->arcs[i][j]=MaxInt;
}
}
for(int i=0;i<MVNum;i++){
a->vex[i] = 0;
store[cunt][i] = 0;
ismin[i] = 0;
}
}
int getIndex(AMGraph *a,char c){ //获取节点在图中的位置
int rs;
for(int i=0;i<a->Vexnum;i++){
if(c==a->vex[i])return i;
}
}
void show(int a[]){ //输出数据
printf("\n[RES]:\n");
printf("最短距离:%d\n",a[0]); //第一位为数字，直接输出
printf("最短路径:%c",a[1]);
for(int i=2;i<MVNum;i++){ //后面皆为字符;
if(a[i] == 0){
break;
}
printf("->%c",a[i]);
}
}
void Dijsktra(AMGraph *a,char s,char e){
int min=0;//记录每一趟的最小值以及该节点
char minv;
int *lgti = (int*)malloc(sizeof(int)*a->Vexnum); //该数组用于更新节点节点的最短路径
char ** lgtc = (char**)malloc(sizeof(char*)*a->Vexnum); //该数组用于保存每个节点当前最短路径
for(int i=0;i<a->Vexnum;i++){ //初始化
lgtc[i]=(char*)malloc(sizeof(char)*a->Vexnum);
lgtc[i][0] = s;
for(int j=1;j<a->Vexnum;j++)lgtc[i][j]=0;
lgti[i] = MaxInt;
}
minv=s;
for(int i=0;i<a->Vexnum-1;i++){ //每次确定一个最小路径，最多共需v-1趟完成
for(int j=0;j<a->Vexnum;j++){ //每趟对v个节点路径进行更新
//printf("\n%c:new =%d,old =%d\n",a->vex[j],min+a->arcs[getIndex(a,minv)][j],lgti[j]);
if(min+a->arcs[getIndex(a,minv)][j]<lgti[j]){ //若更新节点值小于现有最小值，则更新为改值
lgti[j] = min+a->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]:",cunt+1);
for(int j=0;j<a->Vexnum;j++){
if(lgti[j]<min&&ismin[j]==0){ //若小于min且未定为最小值，则记录
min = lgti[j];
minv = a->vex[j];
}
}
printf("新增最小路径: %c\n",minv);
if(minv==e){
printf("Success!\n");
store[cunt][0] = min;
for(int i=0;i<strlen(lgtc[getIndex(a,e)]);i++){
store[cunt][i+1]=(int)lgtc[getIndex(a,e)][i];
}
cunt++;
break;
}
ismin[getIndex(a,minv)]=1;
}
}
void Cal(AMGraph *a){ //计算结果，Dijsktra
char 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(n==0&&m==0)return 1;
a->Vexnum = n;
a->arcnum =m;
printf("请输入顶点:");
for(int i=0;i<n;i++){
scanf(" %c",&a->vex[i]); //储存节点
}
getchar();
printf("请输入边： \n");
for(int i=0;i<m;i++){ //存储边
scanf(" %c %c %d",&ca,&cb,&lgt);
a->arcs[getIndex(a,ca)][getIndex(a,cb)]=lgt;
}
return 0;
}
int main(){
int flag=0; //记录是否输入停止
AMGraph *a = (AMGraph*)malloc(sizeof(AMGraph));
printf("多组数据，每组数据有 m+3 行。\n第一行为两个整数 n 和 m，分别代表城市个数 n 和路径条数 m。\n第二行有 n 个字符，代表每个城市的名字。\n第三行到第m+2 行每行有两个字符 a 和 b 和一个整数 d，代表从城市 a 到城市 b 有一条距离为 d 的路。\n最后一行为两个字符，代表待求最短路径的城市起点和终点。\n当 n 和m 都等于 0 时，输入结束");
while(1){
Init(a); //初始化图
printf("\n =================| -FZC- |=============== \n\n");
flag = Read(a); //读取信息
if(flag==1){
printf("\n =================| -FZC- |=============== \n\n");
printf("\nFOLLOWING OUTPUI:\n");
printf("共寻径[%d]次\n",cunt);
for(int i=0;i<cunt;i++)show(store[i]);
break;
}
Cal(a); //计算距离并存储结果
}
return 0;
} 以上代码仅供参考，欢迎交流。文章来源地址https://www.toymoban.com/news/detail-763704.html
到了这里，关于数据结构实验任务六 ：基于 Dijsktra 算法的最短路径求解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
