NOJ数据结构实验010——用弗洛伊德算法求赋权图的两点间的最短路径的

妖狐艹你老母 2022-10-15 12:48 22阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

本题主要考察弗洛伊德算法的应用。核心思路是设置一个二维数组D利用三重循环将每一个起点到终点的最短路径长度记录下来。

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VER_NUM 20
    
    
    typedef struct {
        
    	int vertex[MAX_VER_NUM];
    	int weight[MAX_VER_NUM][MAX_VER_NUM];
    	int num_vex;//弧的个数用不上
    }AdjMatrix;
    
    int TargetPath[MAX_VER_NUM];//记录所求路径
    
    AdjMatrix* CreateMatrix(int n);   //构建邻接矩阵
    void Floyd(AdjMatrix A, int D[MAX_VER_NUM][MAX_VER_NUM], int P[MAX_VER_NUM][MAX_VER_NUM]);
    //弗洛伊德算法
    void PrintMinStep(AdjMatrix A, int D[MAX_VER_NUM][MAX_VER_NUM]);   //输出最短路径长度
    
    int main()
    {
        
    	int n;
    	scanf("%d", &n);
    	AdjMatrix* A;
    	A = CreateMatrix(n);
    	int D[MAX_VER_NUM][MAX_VER_NUM];//存储最短路径
    	int P[MAX_VER_NUM][MAX_VER_NUM];//存储最短路线
    	Floyd(*A, D, P);
    	PrintMinStep(*A, D);
    	return 0;
    }
    
    AdjMatrix* CreateMatrix(int n)
    {
           //构建邻接矩阵
    	AdjMatrix* A;
    	A = (AdjMatrix*)malloc(sizeof(AdjMatrix));
    	if (A == NULL) {
        
    		return NULL;
    	}
    	A->num_vex = n;
    	for (int i = 0; i < A->num_vex; i++) {
        
    		for (int j = 0; j < A->num_vex; j++) {
        
    			scanf("%d", &A->weight[i][j]);
    		}
    	}
    	return A;
    }
    
    void Floyd(AdjMatrix A, int D[MAX_VER_NUM][MAX_VER_NUM], int P[MAX_VER_NUM][MAX_VER_NUM])
    {
           //弗洛伊德算法
    	for (int i = 0; i < A.num_vex; i++) {
        
    		for (int j = 0; j < A.num_vex; j++) {
        
    			D[i][j] = A.weight[i][j];
    			P[i][j] = j;
    		}
    	}
    	for (int i = 0; i < A.num_vex; i++) {
        //中间点
    		for (int j = 0; j < A.num_vex; j++) {
        //起点
    			for (int k = 0; k < A.num_vex; k++) {
        //终点
    				if (D[j][k] > D[j][i] + D[i][k]) {
        
    					D[j][k] = D[j][i] + D[i][k];//更新最小路径
    					P[j][k] = P[j][i];//更新最小路径终点
    				}
    			}
    		}
    	}
    }
    
    void PrintMinStep(AdjMatrix A, int D[MAX_VER_NUM][MAX_VER_NUM])
    {
           //输出最短路径长度
    	int n;
    	scanf("%d", &n);
    	int* tmp;
    	tmp = (int*)malloc(sizeof(int) * n);
    	for (int i = 0; i < n; i++) {
        
    		int j, k;
    		scanf("%d%d", &j, &k);
    		tmp[i]=D[j][k];
    	}
    	for (int i = 0; i < n; i++) {
        
    		printf("%d\n", tmp[i]);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221014/d1fe377855dc468fb0d1e481ee6ecded.png