本次代码为实验六:基于 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 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){							//计算结果，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(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;
} 

以上代码仅供参考，欢迎交流。