【编程经验】优秀题解

今天给大家带来一个我站“Manchester”大神写的一份优质题解(j解题思路很清晰)：原题问题：1709: 算法7-16：弗洛伊德最短路径算法：

以下是大神的解题思路啊，注意听好！！（敲黑板）

注意事项:

1）：在下面的代码中为了理解方便，没有定义图的邻接矩阵结构，直接定义了邻接矩阵来求解该问题

2）：题目输入0表示无穷，要把输入的非对角线上的0变为无穷

3）：最后在输出的时候，注意，没有路径的两个顶点间，即路径为无穷的，输出-1

参考代码:

#include<stdio.h>

#include<malloc.h>

int MAX_INT=11111;/*定义无穷，表示两个点之间没有边*/

void Floyd(int **Egde,int n);/*Edge为邻接矩阵，n为定点个数*/

int **Creat_space(int n);/*为矩阵分配空间*/

void Free_space(int n,int **Edge);/*释放矩阵空间*/

void in_put(int n,int **Edge);/*输入矩阵*/

void out_put(int n,int Edge[][n]);/*输出矩阵*/

int main()

{

int n;/*定点个数*/

int **Edge;/*邻接矩阵*/

while(scanf("%d",&n)!=EOF)

{

Edge=Creat_space(n);/*创建空间*/

in_put(n,Edge);/*输入矩阵*/

Floyd(Edge,n);/*求最路径矩阵*/

Free_space(n,Edge);/*释放矩阵空间*/

}

return 0;

}

/*----------------------------------------------------------------*/

int **Creat_space(int n)/*为矩阵分配空间*/

{

int **Edge=(int **)malloc(n*sizeof(int *));

for(int i=0;i<n;i++)

Edge[i]=(int *)malloc(n*sizeof(int));

return Edge;

}

/*----------------------------------------------------------------*/

void Free_space(int n,int **Edge)/*释放矩阵空间*/

{

for(int i=0;i<n;i++)

free(Edge[i]);

free(Edge);

}

/*----------------------------------------------------------------*/

void in_put(int n,int **Edge)/*输入矩阵*/

{

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

{

scanf("%d",&Edge[i][j]);

if(i!=j&&Edge[i][j]==0)

Edge[i][j]=MAX_INT;/*把除了主对角线以外的0变为无穷*/

}

}

/*----------------------------------------------------------------*/

void out_put(int n,int Edge[][n])/*输出矩阵*/

{

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

if(Edge[i][j]!=MAX_INT)

printf("%d ",Edge[i][j]);

else

printf("-1 ");/*无穷远时输出-1*/

}

printf("\n");/*行尾换行*/

}

}

/*----------------------------------------------------------------*/

void Floyd(int **Edge,int n)/*Edge为领邻接矩阵，n为定点个数*/

{

int A[n][n];/*定义最小距离矩阵*/

/*矩阵初始化*/

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

{

A[i][j]=Edge[i][j];

}

for(int k=0;k<n;k++)/*k为基准点*/

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

{

if(A[i][j]>(A[i][k]+A[k][j]))

A[i][j]=A[i][k]+A[k][j];

}

/*输出最短路径矩阵*/

out_put(n,A);

}