数据结构-Floyd(弗洛伊德)最短路径算法-题解(关键5行算法）

#include<stdio.h>
#include<math.h>
#define M 100
#define Max 9999
int main(){
    int n,e[M][M]={0};
    int i,j,k;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%d",&e[i][j]);
            if(e[i][j]==0)
                e[i][j]=Max;
        }
    }
 for(k=0;k<n;k++){      //这是关键的几行代码
    for(i=0;i<n;i++){   //本质就是想看看“小哈”从i到j这个点，看有没有k点，让“小哈”从i先到k，然后再从k到j。如果有这么一个点，就看看小哈从i“直接”到j的距离近，还是让小哈“间接”从i到j的距离近
        for(j=0;j<n;j++){
            if(i==j)
                continue;
                if(e[i][k]+e[k][j]<e[i][j])//这里就是是引入k这个中间点了，如果小哈  “直接”  从i到j这个点的距离  比它 “间接”  从i到j这个点的距离 远，就改变e[i][j],也就是改变原来直接从i到j的距离
                    e[i][j]=e[i][k]+e[k][j];
            }
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(e[i][j]==Max&&i!=j)
                e[i][j]=-1;
            if(e[i][j]==Max&&i==j)
                e[i][j]=0;
            printf("%d ",e[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    return 0;
}