Manchester-弗洛伊德最短路径算法

解题思路:

  该算法需要知道其求解过程即可轻松写出代码，将下面的求解过程手动写一遍就可清晰知道代码执行过程，

以下path[]用来记录两节点间的最短路径，对于这道题可以不管。

注意事项:

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);

}

别忘点赞哦-.-