赋权有向图中心问题.ppt

《赋权有向图中心问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、赋权有向图中心问题计算机<1>班余志萍问题描述:设G=(V,E)是一个赋权有向图，v是G的一个顶点，v的偏心距定义为：Max{w∈V,从w到v的最短路径长度}G中偏心距最小的顶点称为G的中心。试利用Floyd算法设计一个求赋权有向图中心的算法。实验任务对于给定的赋权有向图G,计算图的中心。由文件input.txt给出输入数据。第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边，顶点编号为1,2,…,n。接下来的m行中，每行有3个正整数n,v,w,表示图G的一条边(u,v)及其边权w。将计算出的图的中心及其偏心距输出到文件ou

2、tput.txt。第1行是中心的偏心距，第2行是中心的纺号。输入文件示例Input.txt57124132158244255341453输出文件示例Output.txt23解题思路：根据题目中提供的信息可知，输入文件中从第２行开始没行都是输入两个顶点以及他们所夹的边．所以我们可以用邻接矩阵实现赋权有向图的方式来存储有向图.1.读入数据，动态定义一个二维数组a[n+1][n+1]实现赋权有向图的结构例如:Input.txt57a[n+1][n+1]：124a[1]a[２]a[３]a[４]a[５]132可表示为１∞42∞8158２∞　∞

3、　∞45244３∞　∞　∞1∞255４∞　∞　∞　∞3341５∞　　∞∞　∞∞4532.开辟一个动态数组c[n+1][n+1]，利用Floyd算法算出所有顶点对之间的最短路径则：c[n+1][n+1]：c[1]c[1]c[1]c[1]c[1]１　０　４　２　３　６２∞　０　∞　４　５３∞　∞　０　１　４４∞　∞　∞　０　３５　∞　∞　∞　∞　０3.在比较c[n+1][n+1]中的每一列中的最大值即为该列所对应的顶点的偏心距，开辟一个动态数组max[n+1]，存放每个顶点的偏心距max[n+1]：042464.从max[n+1]中找出

4、偏心距最小的顶点并输出其偏心距及编号核心代码：for(i=1;i<=n;i++)//求出所有顶点对的最短距离for(j=1;j<=n;j++){c[i][j]=a[i][j];}for(i=1;i<=n;i++)c[i][i]=0;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++){t1=c[i][k];t2=c[k][j];t3=c[i][j];if(t1!=32768&&t2!=32768&&(t3==32768

5、

6、t1+t2

7、1;j<=n;j++)//求所有顶点的偏心距for(i=1;i<=n;i++)if((c[i][j]>max[j])&&(c[i][j]!=32768))max[j]=c[i][j];dis=32768;center=0;//找出最小的偏心距for(i=1;i<=n;i++)if(max[i]