实验报告

课程名称:《算法分析与设计》
实验日期: 2021年 3月 16日 至 2021 年 3 月 18 日
学生姓名: 甘世伟
所在班级: 计科195
学号: 2019212212053
实验名称: Dijkstra算法
实验地点: 勤园13-218
同组人员: 无
——————————————

1. 问题
   floyd算法求任意两点之间的最短路（实质上是动态规划：
   算法原理：i、j 两点间的最短路径只有两种情况：直接从 i 到 j 或者通过中转点。
   设map[i][j][k]表示从 i 到 j ，以 0—— k 号点作为中转点所能得到的最大值。以 0 作为中转点就表示 i 直接到j，不通过其他点中转点；可以从1到k号点钟选取若干点作为中转点，也可以直接不选取任何点作为中转点。
   那么状态转移方程如下：
   map[i][j][k]=min{map[i][j][k],map[i][k][k-1]+map[k][j][k-1]}
2. 解析
   
   贪心寻找局部最优解，每次寻找剩下的点中距离最近的点，将该点加入中转点，直到所有 顶点访问完毕。
3. 设计
   核心代码

void Dijkstra(int map[8][8],char ver[8][2]) {
	int visit[8] = { 0 };
	char route[8][8][64] ={'#'};
	for (int a = 0; a < 8; a++) {
		for (int b = 0; b < 8; b++) {
			if (map[a][b] != Inf) {
				strcpy(route[a][b], ver[a]);
				strcat(route[a][b], ver[b]);
			}
		}
	}
	int tap[8] = { 0 };
	tap[0] = 1;
	for (int a=1; a < 8; a++) {
		int min = Inf;	
		int minb = 0;
		for (int b = 1; b < 8; b++) {
			for (int c = 0; c < 8; c++) {
				if (tap[c]) {
					if ((map[c][b] < min) && (tap[b] == 0)) {
						min = map[c][b];
						minb = b;
					}
				}
			}
		}
		tap[minb] = 1;
		for (int a1 = 0; a1 < 8; a1++) {
			for (int b = 0; b < 8; b++) {
				if ((map[a1][minb] + map[minb][b]) < map[a1][b]) {
					map[a1][b] = map[a1][minb] + map[minb][b];
					strcpy(route[a1][b], route[a1][minb]);
					route[a1][b][strlen(route[a1][b])-1] = '\0';
					strncat(route[a1][b], route[minb][b],8);
				}
			}
		}
	}
	printf("a到h的路径为:%s\n",route[0][7]);
	printf("a到h的路径距离为:%d",map[0][7]);
}

4.分析
5. 源码
https://github.com/fxgn123/AlgorithmDesign/blob/fxgn123-patch-lab2-2/main.cpp