《赋权有向图中心问题(课堂PPT).ppt》由会员分享，可在线阅读，更多相关《赋权有向图中心问题(课堂PPT).ppt（11页珍藏版）》请在三一文库上搜索。
1、1,赋权有向图中心问题,计算机班 余志萍,2,问题描述: 设G=(V,E)是一个赋权有向图，v是G的一个顶点， v的偏心距定义为： Max w V,从w到v的最短路径长度 G中偏心距最小的顶点称为G的中心。试利用Floyd 算法设计一个求赋权有向图中心的算法。,3,实验任务,对于给定的赋权有向图G,计算图的中心。 由文件input.txt给出输入数据。第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边，顶点编号为1,2,n。接下来的m行中，每行有3个正整数n,v,w,表示图G的一条边(u,v)及其边权w。 将计算出的图的中心及其偏心距输出到文件output.txt。第1行是中心的偏心距
2、，第2行是中心的纺号。,4,输入文件示例 Input.txt 5 7 1 2 4 1 3 2 1 5 8 2 4 4 2 5 5 3 4 1 4 5 3,输出文件示例 Output.txt 2 3,5,解题思路： 根据题目中提供的信息可知，输入文件中从第行开始没行都是输入两个顶点以及他们所夹的边所以我们可以用邻接矩阵实现赋权有向图的方式来存储有向图. 1.读入数据，动态定义一个二维数组an+1n+1实现赋权有向图的结构 例如:Input.txt 5 7 an+1n+1 ： 1 2 4 a1aa a a 1 3 2 可表示为 4 2 8 1 5 8 45 2 4 4 1 2 5 5 3 3 4
3、1 4 5 3,6,2.开辟一个动态数组c n+1 n+1，利用Floyd算法算出所有顶点对之间的最短路径则： c n+1 n+1 ：c1c1c1c1c1 3.在比较c n+1 n+1中的每一列中的最大值即为该列所对应的顶点的偏心距，开辟一个动态数组max n+1，存放每个顶点的偏心距 max n+1：04246 4.从maxn+1中找出偏心距最小的顶点并输出其偏心距及编号,7,核心代码：for (i=1;i=n;i+) /求出所有顶点对的最短距离 for (j=1;j=n;j+) cij=aij; for (i=1;i=n;i+) cii=0; for (k=1;k=n;k+) for (i=1;i=n;i+) for (j=1;j=n;j+) t1=cik; t2=ckj; t3=cij; if (t1!=32768 ,8,for (j=1;jmaxj),9,算法复杂度的计算：,因为利用Floyd算法算，所以时间复杂度为O(n),10,Thank you,素材和资料部分来自网络，如有帮助请下载!,