数据结构实验任务六 ：基于 Dijsktra 算法的最短路径求解_基于dijsktra算法的最短路径求解

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

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