Manchester


私信TA

用户名:wenyajie

访问量:266462

签 名:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

等  级
排  名 1
经  验 54545
参赛次数 1
文章发表 188
年  龄 0
在职情况 学生
学  校 Xiamen University
专  业 计算机科学

  自我简介:

在历史前进的逻辑中前进,这个逻辑就是人心向背的逻辑

解题思路:

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

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

TIM截图20180521200735.png

TIM截图20180521200256.png

TIM截图20180521200324.png

TIM截图20180521200432.png



注意事项:

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

}

别忘点赞哦-.-

 

0.0分

6 人评分

  评论区