第十二届蓝桥杯省赛 C/C++大学B组 试题E：路径

试题题目：

本题答案：10266837
解题思路：

1、思考
   关于最短路径问题，有很多种算法的，例如： D i j k s t r a Dijkstra Dijkstra算法， B e l l m a n − F o r d Bellman-Ford Bellman−Ford算法， F l o y d Floyd Floyd算法和 S P F A SPFA SPFA算法等。关于 D i j k s t r a Dijkstra Dijkstra（迪杰斯特拉）算法用来解决单源的，无负权值的最短路径问题，能求出从起点到某一点的最短路径，在稀疏图的情况下，算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，时效性比较好； F l o y d Floyd Floyd(弗洛伊德)算法是解决多源的，无负权边的最短路径问题，算法的时间复杂度为 O ( n 3 ) O(n^3) O(n3)； B e l l m a n − F o r d Bellman-Ford Bellman−Ford算法是求解单源最短路径问题的一种算法，与 D i j k s t r a Dijkstra Dijkstra（迪杰斯特拉）算法不同的是：边的权值可以是负权值的； S P F A SPFA SPFA算法是 B e l l m a n − F o r d Bellman-Ford Bellman−Ford的队列优化，时效性相对好，时间复杂度 O ( k E ) O(kE) O(kE)。这题我给出了 D i j k s t r a Dijkstra Dijkstra算法和 F l o y d Floyd Floyd算法的解决代码。

2、 F l o y d Floyd Floyd算法解题
   根据题目给出的要求：两点间值的差的绝对值小于等于 21 21 21时，该两点之间有边，边的权值是两点间值的最小公倍数。首先需要初始化图，这里初始化图成单向图，也就是说，只能从点小的向点大的方向走，初始化图的结果部分如下图所示：

   使用简单易理解的 F l o y d Floyd Floyd(弗洛伊德)算法：计算出起点 1 1 1到终点 2021 2021 2021的最短路径，那么需要借用第三个点： K K K。计算从点 1 1 1到点 K K K的最短路径，加上从点 K K K到终点 2021 2021 2021的最短路径。同样的方法，当用循环遍历完所有两点间的最短路径，即可求出点 1 1 1到达点 2021 2021 2021的最短路径。 C C C语言代码如下：

#include
#define INF 99999999
#define MAXV 2022
int D[MAXV][MAXV];
int gcd(int m,int n);
void Floyd(int Vet){
	int i,j,k;
	
	for(i=1;i
		for(k=i+1;k
			for(j=i+1;j<=Vet;j++){
				if(k < j){
					D[i][j] = D[i][j] < D[i][k]+D[k][j]? D[i][j] : D[i][k]+D[k][j];
				}
			} 
		}
	}
}
int main(){
	int i,j;
	for(i=1; i                        //建立图，单向图，并计算出所有的路劲权值
		for(j=1; j
			if(j-i <= 21 && j!=i) D[i][j] = gcd(i,j);
			else D[i][j] = INF;
		}
	}
	Floyd(2022);
	printf("1 --> 2021 的最短距离是 %d nn",D[1][2021]);
	return 0;
} 
int gcd(int m,int n){
	long long int mul = m*n;
	if(m < n){
		int step = m;  m = n;  n = step;
	}
	int y;  y = m%n;
	while(y){
		m = n;  n = y;  y = m%n;
	}
	return mul/n;
}

3、 D i j k s t r a Dijkstra Dijkstra算法解题
   由于 F l o y d Floyd Floyd算法的时间复杂度太高，计算出结果太慢，容易产生“答案是否正确”的误会。算法学习，要靠经验积累。我们了解到 D i j k s t r a Dijkstra Dijkstra算法要比 F l o y d Floyd Floyd算法时效性好，但是理解起来不会特别容易。
   D i j k s t r a Dijkstra Dijkstra算法中设置了三个数组 G [ M A X V ] [ M A X V ] G[MAXV][MAXV] G[MAXV][MAXV]用来初始化图，记录两点间的权值； D [ M A X V ] D[MAXV] D[MAXV]用来记录起点 s s s到达某点 M A X V MAXV MAXV的最短路径； V I S [ M A X V ] VIS[MAXV] VIS[MAXV]用来标记某点 M A X V MAXV MAXV是否被访问过，被访问过标记为 1 1 1，未被访问过标记为 0 0 0。算法有 M A X V MAXV MAXV次循环，每次循环中，都借用第三点 u u u，先是一次循环找出第一个点 u u u，使得 D [ u ] D[u] D[u]最小，也就是起点到点 u u u的最短距离。再次循环，若存在某个点 k k k，使得点 u u u到达点 k k k的距离 G [ u ] [ k ] G[u][k] G[u][k]加上 D [ u ] D[u] D[u]的和，小于原先的 D [ k ] D[k] D[k]，便刷新了 D [ k ] D[k] D[k]的值，从而找到了起点到达点 k k k的最短路径。进入下一次循环，当 D [ k ] D[k] D[k]被重新赋值了，循环中的 u u u被 k k k赋值了。直到寻找到 D [ 2021 ] D[2021] D[2021]止，便输出 D [ 2021 ] D[2021] D[2021]。 C C C语言代码如下：

#include
#define MAXV 2022
#define INF 99999999 
int D[MAXV];        // 起点1  到达各个 顶点的最短路径数组。
int G[MAXV][MAXV];  // 从某一点到另一点的距离数组。
int VIS[MAXV];      // 用来记录点是否被访问过。
int gcd(int m,int n);
void Dijkstra(int s){
	int i,j,k;
	for(i=0;i D[i] = INF;}   
 	for(i=0;i
		int u = -1,MIN = INF;
		D[s] = 0;                       //点到同一个点的距离为0 才能进入下一个点。 
		for(j=0;j
			if(VIS[j]==0 && D[j]
				u = j;
				MIN = D[j];
			}
		}
		if(u==-1){   return;  }             //没有点可以走了； 
		VIS[u] = 1;
		for(k=1; k
			if(VIS[k]==0 && G[u][k]!=INF && D[u] + G[u][k] < D[k] )
			{
				D[k] = D[u]+G[u][k];
			}
		}
	}
}
int main(){
	int i,j;
	for(i=1;i
		for(j=1;j
			if(j-i<=21 && j!=i)  G[i][j] = gcd(j,i);
			else{
				G[i][j] = INF;
			}
		}
	}
	Dijkstra(1);
	printf("从1到 2021 的最短路径为 %d n",D[2021]);
	return 0;	
}
int gcd(int m,int n)
{
	long long int mul = m*n;
	if(m < n){ int step = m;  m = n;  n = step; }
	int y;  y = m%n;
	while(y){  m = n;  n = y;  y = m%n; }
	return mul/n;
}