Floyd算法求各个顶点的最短距离-算法分析与实践作业2-1
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Floyd算法求各个顶点的最短距离-算法分析与实践作业2-1,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2354字,纯文字阅读大概需要4分钟。
内容图文
![Floyd算法求各个顶点的最短距离-算法分析与实践作业2-1](/upload/InfoBanner/zyjiaocheng/639/1991aa5cf27346efa962f3cd1854c63b.jpg)
1.问题
用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵(顶点之间的最短距离矩阵)
2.解析
上图中有4个城市8条公路,公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程,也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。
现在需要一个数据结构来存储图的信息,我们仍然可以用一个4*4的矩阵(二维数组e)来存储。比如1号城市到2号城市的路程为2,则设e[1][2]的值为2。2号城市无法到达4号城市,则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0,例如e[1][1]为0。
我们来想一想,根据我们以往的经验,如果要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点(顶点k),并通过这个顶点k中转即a->k->b,才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢?甚至有时候不只通过一个点,而是经过两个点或者更多点中转会更短,即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4号城市到3号城市(4->3)的路程e[4][3]原本是12。如果只通过1号城市中转(4->1->3),路程将缩短为11(e[4][1]+e[1][3]=5+6=11)。其实1号城市到3号城市也可以通过2号城市中转,使得1号到3号城市的路程缩短为5(e[1][2]+e[2][3]=2+3=5)。所以如果同时经过1号和2号两个城市中转的话,从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子,我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。
3. 设计
1. #include
2. int main()
3. {
4. int e[10][10],k,i,j,n,m,t1,t2,t3;
5. int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
6.
7. //读入n和m,n表示顶点个数,m表示边的条数
8. scanf("%d %d",&n,&m);
9.
10. //初始化
11. for(i=1;i<=n;i++)
12. for(j=1;j<=n;j++)
13. if(i==j)
14. e[i][j]=0;
15. else
16. e[i][j]=inf;
17.
18. //读入边
19. for(i=1;i<=m;i++)
20. {
21. scanf("%d %d %d",&t1,&t2,&t3);
22. e[t1][t2]=t3;
23. }
24.
25. //Floyd-Warshall算法核心语句
26. for(k=1;k<=n;k++)
27. for(i=1;i<=n;i++)
28. for(j=1;j<=n;j++)
29. if(e[i][j]>e[i][k]+e[k][j] )
30. e[i][j]=e[i][k]+e[k][j];
31.
32. //输出最终的结果
33. for(i=1;i<=n;i++)
34. {
35. for(j=1;j<=n;j++)
36. {
37. printf("%10d",e[i][j]);
38. }
39. printf("\n");
40. }
41.
42. return 0;
43. }
4. 源代码地址
https://github.com/Lin02993/-
内容总结
以上是互联网集市为您收集整理的Floyd算法求各个顶点的最短距离-算法分析与实践作业2-1全部内容,希望文章能够帮你解决Floyd算法求各个顶点的最短距离-算法分析与实践作业2-1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。