解题思路:

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

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

TIM截图20180521200735.png

TIM截图20180521200256.png

TIM截图20180521200324.png

TIM截图20180521200432.png



注意事项:

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

2):题目输入0表示无穷,要把输入的非对角线上的0变为无穷

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


参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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);
 
}

别忘点赞哦-.-

点赞(7)
 

9 分

5 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论